[Bug translator/2051] New: Use _stp_map_sortn()

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[Bug translator/2051] New: Use _stp_map_sortn()

glaubitz at physik dot fu-berlin.de
See http://sourceware.org/bugzilla/show_bug.cgi?id=1379 comment 4

In a polling loop, we generally don't need or want to print out an entire sorted
array. sortn() just finds the top or bottom n elements. In a typical array of
1000 elements, sortn(10) runs in less than a tenth the time that sort() takes.
Plus, if the array is not cleared, sortn() will have to do little work and the
speed advantage will become even larger.

Sorts are expensive and lock maps for a long time. So reducing the time the
sorts take will improve accuracy by reducing the number of drops caused by
attempted locks on maps failing.

--
           Summary: Use _stp_map_sortn()
           Product: systemtap
           Version: unspecified
            Status: NEW
          Severity: minor
          Priority: P3
         Component: translator
        AssignedTo: systemtap at sources dot redhat dot com
        ReportedBy: hunt at redhat dot com


http://sourceware.org/bugzilla/show_bug.cgi?id=2051

------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.
Reply | Threaded
Open this post in threaded view
|

[Bug translator/2051] Use _stp_map_sortn(), via iteration-limited foreach

glaubitz at physik dot fu-berlin.de

------- Additional Comments From fche at redhat dot com  2005-12-13 21:26 -------
This naturally ties in to iteration-limited array iteration.  To express this in
the language, one way is to extend the grammar in a way reminiscent of SQL:

foreach ([i1,i2] in ray limit N) {
}

where N is a numeric expression evaluated at the beginning, and doesn't need to
be a literal.  The sorting +/- directives would stay as/where they are with
current rules.

How does the runtime sortn compare with sort for N approaching the map size?


--
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|minor                       |normal
           Priority|P3                          |P2
            Summary|Use _stp_map_sortn()        |Use _stp_map_sortn(), via
                   |                            |iteration-limited foreach


http://sourceware.org/bugzilla/show_bug.cgi?id=2051

------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.
Reply | Threaded
Open this post in threaded view
|

[Bug translator/2051] Use _stp_map_sortn(), via iteration-limited foreach

glaubitz at physik dot fu-berlin.de
In reply to this post by glaubitz at physik dot fu-berlin.de

------- Additional Comments From hunt at redhat dot com  2005-12-13 21:38 -------
Subject: Re:  Use _stp_map_sortn(), via
        iteration-limited foreach

On Tue, 2005-12-13 at 21:26 +0000, fche at redhat dot com wrote:
> How does the runtime sortn compare with sort for N approaching the map size?

For small map sizes, both sorts are close in speed. But sortn()
approaches n**2 as N approaches the size of the map. I'd say just limit
N to 30 for sortn(), otherwise go with sort().




--


http://sourceware.org/bugzilla/show_bug.cgi?id=2051

------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.
Reply | Threaded
Open this post in threaded view
|

[Bug translator/2051] Use _stp_map_sortn(), via iteration-limited foreach

glaubitz at physik dot fu-berlin.de
In reply to this post by glaubitz at physik dot fu-berlin.de

------- Additional Comments From weikong at redflag-linux dot com  2005-12-14 02:22 -------
Some time what I want to sort is not the value, but some key.
 
How? can?  

--


http://sourceware.org/bugzilla/show_bug.cgi?id=2051

------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.
Reply | Threaded
Open this post in threaded view
|

Re: sorting

Frank Ch. Eigler
In reply to this post by glaubitz at physik dot fu-berlin.de
Hi -

weikong wrote:

> Some time what I want to sort is not the value, but some key.
> How? can?  

Yes.  As the man page points out, you can put the "+" or "-" sorting
directive on an index in the foreach loop:

          foreach ([a,b-] in arr) { }

Then the iteration will be in decreasing order of the second key.

- FChE