elp: gnus-article-sort-by-number run 664 times?

elp: gnus-article-sort-by-number run 664 times?

[jari.aalto]

    I was studying what gnus does when I enter a group with SPC and
    I got this. I'm wondering why so high call count as 664 for
    a group (mail.emacs) which only has 173 articles?

    Am I imaginating or is Gnus do something extra than needed?
    This is vanilla Gnus with no gnus.el.  

    jari

[top elp.el results]

Function Name                    Call Count  Elapsed Time  Average Time
================================  ==========  ============  ============
gnus-group-read-group             1           37.413530999  37.413530999
gnus-summary-read-group           1           37.385351     37.385351
gnus-summary-read-group-1         1           37.384737000  37.384737000
gnus-summary-prepare              1           20.769714     20.769714
gnus-sort-threads                 1           11.856545000  11.856545000
gnus-thread-sort-by-number        664         10.532257000  0.0158618328
gnus-article-sort-by-number       664         9.7256939999  0.0146471295
gnus-run-hooks                    180         8.1762829999  0.0454237944
nus-summary-first-unread-article  1           7.0342459999  7.03424

Re: elp: gnus-article-sort-by-number run 664 times?

[Alan Shutko]

>>>>> "J" == jari aalto <jari.aalto@poboxes.com> writes:

J>     I was studying what gnus does when I enter a group with SPC and
J> I got this. I'm wondering why so high call count as 664 for a group
J> (mail.emacs) which only has 173 articles?

That's because qsort is O(n lg n).

-- 
Alan Shutko <ats@acm.org> - By consent of the corrupted
Sex on TV can't hurt you unless you fall off!

Re: elp: gnus-article-sort-by-number run 664 times?

[Colin Rafferty]

jari aalto writes:

>     I was studying what gnus does when I enter a group with SPC and
>     I got this. I'm wondering why so high call count as 664 for
>     a group (mail.emacs) which only has 173 articles?

If you can come up with a sorting algorithm that has better than
n*log(n) complexity, let me know.

-- 
Colin

Re: elp: gnus-article-sort-by-number run 664 times?

[Paul Franklin]

>>>>> Colin Rafferty writes:

 > jari aalto writes:

 >>     I was studying what gnus does when I enter a group with SPC and
 >>     I got this. I'm wondering why so high call count as 664 for
 >>     a group (mail.emacs) which only has 173 articles?

 > If you can come up with a sorting algorithm that has better than
 > n*log(n) complexity, let me know.

Well, the function is called "gnus-thread-sort-by-number", and I would 
be willing to bet that gnus starts with ordered message numbers, so it 
seems like an insertion sort which first tried the bottom before doing 
a lg(n) search would perform well if you didn't have many threads.

The next time I get bored with real work, maybe I'll instrument the
code to see if they do come in order, then see if I can come up with
some nice way of dealing well with both cases.

--Paul

Re: elp: gnus-article-sort-by-number run 664 times?

[Alan Shutko]

>>>>> "P" == Paul Franklin <paul@cs.washington.edu> writes:

P> Well, the function is called "gnus-thread-sort-by-number"

Actually, that function is just the qsort comparison function.  The
real work is done in gnus-sort-threads.  That's why
gnus-thread-sort-by-number gets called so much.

I'm not sure you could change it so much, because it looks like the
multiple gnus-sort-by exist so we can choose how we sort things, and
gnus just passes in a compare function....

-- 
Alan Shutko <ats@acm.org> - By consent of the corrupted
E Pluribus Unix

Re: elp: gnus-article-sort-by-number run 664 times?

[jari.aalto]

| 98-03-19 Paul Franklin <paul@cs.washington.edu> list.ding
| >>>>> Colin Rafferty writes:
|  > If you can come up with a sorting algorithm that has better than
|  > n*log(n) complexity, let me know.
| 
| Well, the function is called "gnus-thread-sort-by-number", and I would 
| be willing to bet that gnus starts with ordered message numbers, so it 
| seems like an insertion sort which first tried the bottom before doing 
| a lg(n) search would perform well if you didn't have many threads.
| 
| The next time I get bored with real work, maybe I'll instrument the
| code to see if they do come in order, then see if I can come up with
| some nice way of dealing well with both cases.


This is what I've got from gnus-thread-sort-by-number
when printing 

    COUNT 
    (elt (car h1) 0) 
    (elt (car h2) 0)

jari

|0| >> |61|2140|
|1| >> |723|534|
|2| >> |534|358|
|3| >> |358|61|
|4| >> |358|2140|
|5| >> |534|2140|
|6| >> |723|2140|
|7| >> |896|895|
|8| >> |1282|1184|
|9| >> |1184|934|
|10| >> |934|895|
|11| >> |934|896|
|12| >> |895|61|
|13| >> |895|358|
|14| >> |895|534|
|15| >> |895|723|
|16| >> |895|2140|
|17| >> |896|2140|
|18| >> |934|2140|
|19| >> |1184|2140|
|20| >> |1282|2140|
|21| >> |1413|1285|
|22| >> |1785|1684|
|23| >> |1684|1472|
|24| >> |1472|1285|
|25| >> |1472|1413|
|26| >> |2018|1982|
|27| >> |1982|1926|
|28| >> |2133|2127|
|29| >> |2127|2037|
|30| >> |2037|1926|
|31| >> |2037|1982|
|32| >> |2037|2018|
|33| >> |1926|1285|
|34| >> |1926|1413|
|35| >> |1926|1472|
|36| >> |1926|1684|
|37| >> |1926|1785|
|38| >> |1285|61|
|39| >> |1285|358|
|40| >> |1285|534|
|41| >> |1285|723|
|42| >> |1285|895|
|43| >> |1285|896|
|44| >> |1285|934|
|45| >> |1285|1184|
|46| >> |1285|1282|
|47| >> |1285|2140|
|48| >> |1413|2140|
|49| >> |1472|2140|
|50| >> |1684|2140|
|51| >> |1785|2140|
|52| >> |1926|2140|
|53| >> |1982|2140|
|54| >> |2018|2140|
|55| >> |2037|2140|
|56| >> |2127|2140|
|57| >> |2133|2140|
|58| >> |2163|2134|
|59| >> |2220|2193|
|60| >> |2193|2190|
|61| >> |2190|2134|
|62| >> |2190|2163|
|63| >> |2232|2225|
|64| >> |2225|2222|
|65| >> |1714|1499|
|66| >> |1499|1740|
|67| >> |1714|1740|
|68| >> |1499|2222|
|69| >> |1714|2222|
|70| >> |1740|2222|
|71| >> |1499|2134|
|72| >> |1714|2134|
|73| >> |1740|2134|
|74| >> |2222|2134|
|75| >> |2222|2163|
|76| >> |2222|2190|
|77| >> |2222|2193|
|78| >> |2222|2220|
|79| >> |2172|878|
|80| >> |2179|2162|
|81| >> |2162|2228|
|82| >> |2179|2228|
|83| >> |2162|878|
|84| >> |2162|2172|
|85| >> |2179|2172|
|86| >> |2219|2057|
|87| >> |2057|1803|
|88| >> |2116|2055|
|89| >> |2055|2170|
|90| >> |2116|2170|
|91| >> |2055|1803|
|92| >> |2055|2057|
|93| >> |2116|2057|
|94| >> |2116|2219|
|95| >> |2170|2219|
|96| >> |1803|878|
|97| >> |1803|2162|
|98| >> |2055|2162|
|99| >> |2057|2162|
|100| >> |2116|2162|
|101| >> |2170|2162|
|102| >> |2170|2172|
|103| >> |2219|2172|
|104| >> |2219|2179|
|105| >> |2219|2228|
|106| >> |878|1499|
|107| >> |1803|1499|
|108| >> |1803|1714|
|109| >> |1803|1740|
|110| >> |1803|2134|
|111| >> |2055|2134|
|112| >> |2057|2134|
|113| >> |2116|2134|
|114| >> |2162|2134|
|115| >> |2162|2163|
|116| >> |2170|2163|
|117| >> |2170|2190|
|118| >> |2172|2190|
|119| >> |2179|2190|
|120| >> |2219|2190|
|121| >> |2219|2193|
|122| >> |2219|2220|
|123| >> |2228|2220|
|124| >> |2228|2222|
|125| >> |2228|2225|
|126| >> |2228|2232|
|127| >> |878|61|
|128| >> |878|358|
|129| >> |878|534|
|130| >> |878|723|
|131| >> |878|895|
|132| >> |1499|895|
|133| >> |1499|896|
|134| >> |1499|934|
|135| >> |1499|1184|
|136| >> |1499|1282|
|137| >> |1499|1285|
|138| >> |1499|1413|
|139| >> |1499|1472|
|140| >> |1499|1684|
|141| >> |1714|1684|
|142| >> |1714|1785|
|143| >> |1740|1785|
|144| >> |1803|1785|
|145| >> |1803|1926|
|146| >> |2055|1926|
|147| >> |2055|1982|
|148| >> |2055|2018|
|149| >> |2055|2037|
|150| >> |2055|2127|
|151| >> |2057|2127|
|152| >> |2116|2127|
|153| >> |2134|2127|
|154| >> |2134|2133|
|155| >> |2134|2140|
|156| >> |2162|2140|
|157| >> |2219|2018|
|158| >> |2057|2055|
|159| >> |2172|2127|
|160| >> |2140|2134|
|161| >> |2179|2162|
|162| >> |2162|2134|
|163| >> |2162|2140|

Re: elp: gnus-article-sort-by-number run 664 times?

[Andi Kleen]

Alan Shutko <ats@acm.org> writes:

> >>>>> "J" == jari aalto <jari.aalto@poboxes.com> writes:
> 
> J>     I was studying what gnus does when I enter a group with SPC and
> J> I got this. I'm wondering why so high call count as 664 for a group
> J> (mail.emacs) which only has 173 articles?
> 
> That's because qsort is O(n lg n).

And the worst case is O(n ^ 2) for data that is already mostly sorted.
I wouldn't be surprised if that is often the case for newsgroups...
How about switching to introsort, which in most cases does better 
than qsort and doesn't have this ugly worst case?

-Andi

Re: elp: gnus-article-sort-by-number run 664 times?

[Felix Lee]

> > That's because qsort is O(n lg n).
> And the worst case is O(n ^ 2) for data that is already mostly sorted.

sort in emacs 20 is a merge sort, which is O(n lg n)
worstcase.  earlier versions of emacs may have used qsort();
I don't really remember.
--