52523 - Tree columns in Password/Image/Cookie not sortable

Status: VERIFIED FIXED

(SeaMonkey :: Passwords & Permissions, defect, P4)

Description

[Blake Ross]

This is especially important for these trees; please see other dialogs that 
have trees which do this to see how to do it.  (just have to add change the 
class to include the sort arrow image, and add a generic sorting function)

Comment 1

[sairuh (rarely reading bugmail)]

spam: mass-moving open password manager (single signon) and form manager
(autofill) bugs to Terri for qa contact. unfortunately, i cannot cc myself with
this form, so feel free and add me if you want to keep me in the loop with any
(but, pls not all :) of these... will also go thru 'em meself, a bit later...

Comment 2

[Stephen P. Morse]

*** Bug 55083 has been marked as a duplicate of this bug. ***

Comment 3

[Marcia Knous [:marcia]]

Netscape Nav triage team: this is a Netscape beta stopper.

Comment 4

[Stephen P. Morse]

Well this is a bit more difficult than just changing the class.  In fact, the 
changes necessary are:

1. Add script tags for nsTreeController.js and nsTreeUtil.js
2. Add id="theColumns" to <treecolgroup>
3. Add ids to each <treecol> within the <treecolgroup>
4. Change class in each <treecell> from "treecell-header"
   to treecell-header sortDirectionIndicator"
5. Add onclick to each treecell as follows
   onclick="return TriStateColumnSort('<<id picked in step 3 above>>');"

And after doing all that, there's still something missing because it now crashes 
when the sort is attempted (sortInfo->db is null on line 1105 of 
nsXULSortService.cpp).  With a little more debugging, this can probably be 
fixed.

But there's a bigger problem.  The common sort code in nsTreeUtils.js relies on 
having a fixed id for the <treecolgroup>, namely "theColumns" as indicated in 
step 2 above.  However there are four different trees that need sorting in 
CookieViewer.xul and you can't give the same id to all four <treecolgroup>s in 
that file.  To correct this you would have to modify the common sort code and 
therefore modify all the existing callers to that code.

So much for this being a simple change.

Comment 5

[Stephen P. Morse]

The problems I was having was in trying to use the generic TriStateColumnSort in 
nsTreeUtils.js.  Unfortunately that routine is too general in certain areas and 
much too specific in others.  I already pointed out that it relies on fixed id's 
in certain widgets and that precludes the ability of sorting more than one tree 
per dialog.  Furthermore, it relies on the data store using rdf which is the 
case for history and bookmarks but not for cookies and passwords (this was the 
cause of the crash mentioned above).

All that is needed for the cookies and password sorts is a very simple sort 
routine which I have included in a new file called nsWalletTreeUtils.js.  It 
might be nice to have a generic routine to handle all four sorts, but that would 
require some work in the bookmarks and history sections.  Might be something 
somebody would want to do in the future.

The modified files for this patch are:

   extensions/wallet/jar.mn -- includes the new file nsWalletTreeUtils.js
   extensions/wallet/signonviewer/SignonViewer.xul -- hooks to sort routine
   extensions/wallet/cookieviewer/CookieViewer.xul -- hooks to sort routine
   extensions/wallet/cookieviewer/nsWalletTreeUtils.js -- sort routine

Comment 6

[Stephen P. Morse]

Attachment: patch for CookieViewer and SignonViewer xul files

Comment 7

[Stephen P. Morse]

Attachment: new file extensions/wallet/cookieviewer/nsWalletTreeUtils.js

Comment 8

[Stephen P. Morse]

Attachment: corrected nsWalletTreeUtils.js to include MPL instead of NPL

Comment 9

[saari (gone)]

r=saari provided the quickSort routine name is changed to bubbleSort (which is
what it is)

Comment 10

[Stephen P. Morse]

Attachment: nsWalletTreeUtil.js with mis-named quicksort changed to bubblesort

Comment 11

[Stephen P. Morse]

cc'ing alecf for super review.

Comment 12

[Brendan Eich [:brendan]]

      ascending = children.getAttribute('lastAscending');
      if (ascending=='true') {
        ascending=false;
      } else {
        ascending=true;
      }

should be shortened to just

      ascending = (children.getAttribute('lastAscending') == 'true');

Another simplification:

    if ((ascending && cell.getAttribute('value') >
nextCell.getAttribute('value')) ||
        (!ascending && cell.getAttribute('value') <
nextCell.getAttribute('value'))) {

should be

    if (ascending ?
        cell.getAttribute('value') > nextCell.getAttribute('value') :
        cell.getAttribute('value') < nextCell.getAttribute('value')) {

(I put the ? and : at end of line, following || placement style).

More significantly, the JS here iterates over firstChild/nextSibling linked
lists when it could index directly:

    var cell = row.firstChild;
    var nextCell = nextRow.firstChild;
    for (var i=0; i<columnPosition; i++) {
      cell = cell.nextSibling;
      nextCell = nextCell.nextSibling;
    }

should be

    var cell = row.childNodes[columnPosition];
    var nextCell = nextRow.childNodes[columnPosition];

This comment threw me:

 // swap the contents of the two cells and the id's of the corresponding menuitems

It should say "swap the values of the two rows", or "swap cell values in the two
rows", or some such, shouldn't it?

BTW, the sort algorithm used here is *not* bubble-sort: bubble-sort avoids
comparing (and not swapping) items earlier in the list that have already been
sorted, but this bubbleSort always starts at the front of the list.  The
canonical bubble-sort loop structure is

    for (var i = 0; i < a.length - 1; i++)
        for (var j = i + 1; j < a.length; j++)
            if (a[i] and a[j] are out of order)
                swap them;

Both algorithms are O(n**2), but there is no need to re-compare already-sorted
items in the list.

This ability to index into DOM childNodes collections raises the "big picture"
question, which is: why write a bubble-sort function in JS given the fact that
DOM collections look like JS arrays (have int-indexed properties and a length
property equal to one more than the greatest index), and the fact that JS's
Array.prototype.sort method (which uses QuickSort, for O(n*log(n)) complexity)
is generic -- it works on any array-like object?

I'll take a stab at adapting nsWalletTreeUtil.js to use Array.prototype.sort and
attach it here.

/be

Comment 13

[Stephen P. Morse]

Brendan,

You have some excellent suggestions here.  Let me comment on them one by one.

> ascending = children.getAttribute('lastAscending');
> if (ascending=='true') {
>   ascending=false;
> } else {
>   ascending=true;
> }
>
> should be shortened to just
>
>  ascending = (children.getAttribute('lastAscending') == 'true');

That's great (really make me feel stupid for writing what I did).  I was just so 
disgusted that I couldn't write "ascending = !ascending" that I just wrote it 
out the long way in disgust.  I was actually tempted to use ?: notation to 
reduce the number of lines but concluded that that would be less readable.  
However your version is perfect.

> if ((ascending && cell.getAttribute('value') > nextCell.getAttribute('value')) 
> ||(!ascending && cell.getAttribute('value') < nextCell.getAttribute('value'))) 
>
> should be
>
>    if (ascending ?
>        cell.getAttribute('value') > nextCell.getAttribute('value') :
>        cell.getAttribute('value') < nextCell.getAttribute('value')) {

Another good suggestion

>    var cell = row.firstChild;
>    var nextCell = nextRow.firstChild;
>    for (var i=0; i<columnPosition; i++) {
>      cell = cell.nextSibling;
>      nextCell = nextCell.nextSibling;
>    }
>
>should be
>
>    var cell = row.childNodes[columnPosition];
>    var nextCell = nextRow.childNodes[columnPosition];

Excellent.

Finally, I realize that I'm not doing an optimum sort because I resort the 
values that were already sorted.  But I recall from a course that I took many 
years ago (more years than I care to recall) that the teacher did an analysis 
and showed that the test for changing the starting point in the loop on each 
iteration was actually taking more time than the reduced number of comparisons 
saved.  Perhas that analysis was only valid for a particular environment, but 
that has kept me from adding the extra testing whenever writing a bubble sort.

Anyway, if you are really going to do a quicksort (something which I was going 
to play around with if I had time after getting this checked in), that would be 
the best solution.  Thanks.

Comment 14

[Brendan Eich [:brendan]]

JS's quick-sort is C code underlying the native Array.prototype.sort method.  A
while ago, I filed a bug suggesting that all DOM collections (NodeList) delegate
to Array.prototype so as to "inherit" all the generic JS array methods.  That
bug got marked WONTFIX, by me, IIRC -- mainly because the w3c DOM spec doesn't
specify any such extension, and it's not clear in allowing such an extension.

BTW, I think you can write 'ascending = !ascending' in JS, although if the value
of ascending is "true" or "false", you'll always set ascending to false.  One
way around that is to write 'ascending = !eval(ascending)', but eval is costlier
than the == test I suggested, which synthesizes a boolean value.

Patch coming next, although it won't be tested!  Testing help will be greatly
appreciated.

/be

Comment 15

[Brendan Eich [:brendan]]

Attachment: My attempt to use true bubble-sort

Comment 16

[Brendan Eich [:brendan]]

Also, and I'm cc'ing hecker here for advice, and apologizing up front for not
having a clearer policy posted at http://www.mozilla.org: I think the best
course in the short run is to keep Netscape-com-copyrighted files under the NPL.
We are in the middle of a lengthy relicensing procedure that involves getting
permission to change to some kind of dual or triple license, or perhaps just to
change the NPL so as to allow its use under GPL or LPGL.

I'm so not expert, but I wanted to spread a bit of hecker's wisdom here and get
the right short-term license on the new files in this bug, provided we can't use
the right long-term license (which I do not believe we have in hand yet).  With
the input gathered here, I'll make sure the mozilla.org site is updated with
news on the right license to use on new code, in this interim period before we
settle on the right [L]GPL-friendly license combo.

/be

Comment 17

[Brendan Eich [:brendan]]

Attachment: hearty attempt to use Array.prototype.sort; testing help craved

Comment 18

[Brendan Eich [:brendan]]

I also removed the unused lastAscending variable, and fixed my broken
simplification of ascending's computation from a string-valued attribute.

Please let me know if thing don't work right with the last patch, and any
crashes or console output -- I'll help debug.

/be

Comment 19

[Frank Hecker]

Re Brendan's comment on licensing: If the new source file is created by and 
copyright Netscape, then you can certainly use the NPL. IIRC there are also some 
Netscape-created files under the MPL, so IMO that's a possible option too; it's 
not clear to me exactly what the official Netscape policy is at the moment re 
using the NPL vs. MPL. (You'd probably be better off asking Mitchell about 
this.)

In any case, don't use NPL/GPL, MPL/GPL, or similar dual licensing schemes for 
this code, unless the file is part of a subsystem like JS or NSS that is already 
using such schemes. As Brendan wrote, the long-term licensing scheme has not yet 
been finalized yet.

Comment 20

[Stephen P. Morse]

I haven't tested the so-called "true bubblesort" patch because I'd rather use 
the quicksort patch posted next so I'll be testing that one out shortly.  
However I do have a few comments on the "true bubblesort" patch which, of 
course, are simply academic since we won't be using it.

1. You go through the out loop a.length times.  But it could be that you can 
break out much sooner if no values get swapped during any one pass.

2. You are advancing the starting point on the inner loop on each iteration of 
the outer loop.  Shouldn't you be retarding the ending point instead?

3. You are right about the global variable lastAscending not being used.  Also 
lastColumnPosition as a global variable is not used either.  Both were temporary 
until I added the code to store them in attributes instead of global variables 
because the global variables didn't allow for having several sortable trees in 
the same xul file.

Comment 21

[Stephen P. Morse]

I retract both of my comment above.  You are not comparing adjacent entries as I 
at first thought but rather comparing the first entry to all other entries, the 
second to all others, etc.  So the way you have it is absolutely correct.  
Furthermore I tested it and it indeed does the sort correctly.

Comment 22

[Stephen P. Morse]

Well the true bubblesort works fine as I reported above.  The quicksort (i.e. 
Array.prototype.sort) does not.  The compare function is never being called.  
Still investigating.

Comment 23

[Stephen P. Morse]

The quicksort method is failing in the array_sort method of jsarray.c because 
len is coming up as zero.  Len is computed from

   js_GetLengthProperty(cx, obj, &len)

Not yet sure what this means.

Comment 24

[Brendan Eich [:brendan]]

Here comes a better Array.prototype.sort-based patch. I passed children as the
'this' parameter (the generic array-like object to be sorted), but should have
passed children.childNodes (as that is the array-like object with a length
property that counts its indexed elements).

Also, I forgot to take advantage of the lexical closure formed by nesting
comparewithin Wallet_ColumnSort.  That closure means columnPosition and
ascending will be available with the correct values in the compare function,
found within the activation of Wallet_ColumnSort on the compare activation's
scope chain.

/be

Comment 25

[Brendan Eich [:brendan]]

Attachment: better attempt to use Array.prototype.sort (may still not work if the DOM balks at element swapping in a NodeList)

Comment 26

[Brendan Eich [:brendan]]

I also got rid of the left-over global lastColumnPosition var, and fixed the
indentation and bracing in the if (columnPosition == lastColumnPosition)...else
statement.

If the DOM doesn't support tmp = a[i]; a[i] = a[j]; a[j] = tmp for a NodeList a
then this Array.prototype.sort approach still won't work.  But that would seem
to me to be a DOM bug.  Here's hoping -- morse, can you try that latest patch?
Thanks,

/be

/be

Comment 27

[Alec Flett]

you know, if we just used RDF to assert things into/out of an in-memory
datasource, we would get sorting for free, and would be able to generate other
types of UI from the datasource (such as an autocompletion menu).. something out
of scope for this bug, but it's something to consider for the future.

Comment 28

[Stephen P. Morse]

New patch is better -- now the compare routine is called when it should be and 
is returning the correct answer.

However the DOM element-swapping is not working.  I probably should have 
commented on that earlier because I previously ran into that problem when 
testing my original bubble-sort algorithm.

So it looks like this will be a blocker on the quicksort approach so I suggest 
we stick with the bubble-sort one for now.  That would be the patch 
labelled "My attempt to use true bubble-sort".  Since I didn't write that one 
(brendan did), I'll do the review on it:

   r=morse

and now it's ready for alecf's to do a super-review.

Comment 29

[Scott Collins]

re: brendan's 12/29 licensing comment -- now I feel stupid :-)  I'm the one who
told Steve that we were supposed to be MPL-ing new files.  I was unaware that
there might be a more discriminating policy.  My apologies, Steve.

Comment 30

[Brendan Eich [:brendan]]

Attachment: cleaned up true bubble-sort version

Comment 31

[Brendan Eich [:brendan]]

I fixed the indentation and the modeline, and removed the unused global vars.

/be

Comment 32

[Stephen P. Morse]

r=morse for brendan's latest patch.

Comment 33

[Stephen P. Morse]

Stop.  I'm retracting my r=morse.

There are two gross inefficiences in the algorithm as it now stands.

1. The values of item, cell, keycell, and key are a function of i only, yet they 
are being recomputed in the inner loop every time j changes.  They should be 
computed inside the outerloop each time i changes and held fixed on each 
interation of the inner loop.

2. The swap is being done on each interation of the inner loop for which the 
comparison indicates it is needed, overwriting any previous swaps done in that 
loop.  So the previous swap was unnecessary and could have been skipped.  Swaps 
are very expensive.

Here's some timin that I just obtained for a list of 224 sites to be sorted.  
There are a total of 25,425 comparisons being made.

1a. List is already in sorted order.
   time: 30 seconds

1b. List is sorted backwards and needs to be reversed.
   time: 3 minutes 25 seconds

Now I removed the initialization of item, cell, keycell and key from the inner 
loop.  The new timing is:

2a. List is already in sorted order.
   time: 16 seconds

2b. List is sorted backwards and needs to be reversed.
   time: 3 minutes 14 seconds

And now I modified the algorithm to do only one swap for each iteration of the 
outer loop

3a. List is already in sorted order.
   time: 16 seconds

3b. List is sorted backwards and needs to be reversed.
   time: 16 seconds

Attaching revised patch.  Brendan, please review since I wrote it this time.

Comment 34

[Stephen P. Morse]

Attachment: Bubble sort patch with two inefficiences corrected

Comment 35

[Stephen P. Morse]

Even though the preceding patch gives quite a speed-up (from 210 seconds to 16 
seconds), I still wasn't happy with having to wait 16 seconds for a sort to 
complete.  So I investigated further and discovered that the most expensive 
operation was obtaining the value attribute of a cell which was being done once 
for every comparison (and there are 25,425 comparisons).

So I tried making one pass through the cells and storing the value attributes 
into an array.  That involves obtaining the value attributes only 224 times.  
And the resulting time for the entire sort is now only one second.

Not bad for a days work -- reducing the sort time of 210 seconds down to one 
second!  New patch attached.

Comment 36

[Stephen P. Morse]

Attachment: Next optimization: gets sor time for 224 elements down to one second

Comment 37

[Stephen P. Morse]

Attachment: Same as preceding but with a variable name changed (more readable)

Comment 38

[Stephen P. Morse]

There are a lot of attachments presented here, so let me state which ones are 
still relevant.  The very first attachment (12/28/00 22:08) is for the 
CookieViewer and SignonViewer xul files and is still relevant.  All the other 
attachments are various attempts at the nsWalletTreeUtils.js file and only the 
last one (12/30/00 21:13) is the relevant one.

Comment 39

[Blake Ross]

morse, mind splitting off that crash you saw earlier into a separate bug?  we 
shouldn't crash there regardless.

Comment 40

[Alec Flett]

looks ok to me, but I'd like to hear the final word from brendan.
I've been trying to follow the history on this, but basically it sounds like we
can't do a direct swap of nodes in the DOM tree itself, so we're swapping the
"value" attribute instead? If someone can confirm that I've summarized this
correctly, then sr=alecf

Comment 41

[Brendan Eich [:brendan]]

Nice measurement/optimization work, Steve.

In case it wasn't clear from the history of my attachments to this bug (where I
was aiming to use JS's Array.prototype.sort, not to evolve an ad-hoc sorting
method in nsWalletTreeUtils.js as a checkin candidate), my "true bubble-sort"
version was provided merely to show the correct algorithm, not to get an r= and
rush a checkin of code that needed to be optimized once it was correct.

So I'm glad nothing was checked in, and kudos to morse for measuring twice.

In any event, I would not advocate bubble-sort over QuickSort unless the input
was quaranteed to be small enough, *and* footprint differences or other subtle
trade-offs between the recursive (or equivalent) O(n*log2(n)) QuickSort and an
iterative O(n**2) bubble-sort argued for bubble-sort. See the next two
attachments and run them in the JS shell or in xpcshell for the reason why --
the output of each is the number of "assignments" of one array element to
another (a swap counts for two assignments).

The third attachment from here will be my attempt at nsWalletTreeUtils.js that
uses QuickSort -- testing feedback welcome, but again, I'm not trying to assume
"ownership" of the patch of assignment of this bug!

Standard bubble-sort does indeed assume that swaps are cheap, and morse's
measurements show that for DOM node attributes, that assumption is way wrong.
The time explosion reported in morse's comments dated 12/30 15:03 show O(n**2)
growth, which is what one would expect for bubble-sort.  But the DOM costs are
simply too high in absolute terms, and those costs should be addressed by other
bugs -- I'm cc'ing jst for help filing new bugs or citing existing reports.

Also, jst: why can't we use JS's Array.prototype.sort on a NodeList?  Shouldn't
the SetProperty call work?

Can we spend just a few days trying to fix the DOM or use an in-memory RDF data
source as alecf suggested (RDF uses QuickSort, as JS does)?  I'm willing to help
out in hacking whatever fixes are necessary.

If it turns out that the RDF or DOM in-place sort fixes involve too many lengthy
bug-dependencies, then we can fall back on an ad-hoc sort (QuickSort, I hope,
based on my third upcoming attachment to this bug).  But let's dig a little
deeper into the alternatives that reuse existing sort mechanism, ok?  I don't
think we do right by propagating yet another sort-in-JS (or sort-in-C++, or in
any language ;-) implementation.

Which of course is not to say any existing sort-in-JS impls that I've missed are
ok -- bad on me for missing them.  Anyone know of any such redundancies?

/be

Comment 42

[Brendan Eich [:brendan]]

Attachment: bubble-sort test showing 92 assignments for all combinations of [1,2,3,4]

Comment 43

[Brendan Eich [:brendan]]

Attachment: QuickSort test showing 84 assignments for all combinations of [1,2,3,4]

Comment 44

[Brendan Eich [:brendan]]

Attachment: my attempt to use QuickSort in nsWalletTreeUtils.js

Comment 45

[Brendan Eich [:brendan]]

Attachment: slightly better attempt avoids retesting i < j

Comment 46

[Brendan Eich [:brendan]]

Attachment: even better control flow, avoid retesting invariants, better comments

Comment 47

[Brendan Eich [:brendan]]

Attachment: important(!) bugfix: save and restore pivot attributes

Comment 48

[Brendan Eich [:brendan]]

Apologies for all the patches; I wanted to show stepwise refinement (heh; up
till the last patch, the QuickSort attempt was majorly busted; so much for its
refinement!), and still hope someone will read the versions and enjoy.  The last
one should work, but it has only passed my eye (and its simplified testcase,
quick.js, has tracked the control flow changes and works in the js or xpcshell).
Let me know, thanks.

/be

Comment 49

[Stephen P. Morse]

Timing Analysis using same list of 224 sites as per previous timings

1. Brendan's last quicksort ("important bugfix save and restore ...")

   a. List already sorted:   1.6 seconds
   b. List sorted backwards: 2.5 seconds

2. My last bubblesort ("same as preceding but with variable name changed ...")

   a. List already sorted:   0.3 seconds
   b. List sorted backwards: 1.1 seconds

Comment 50

[timeless]

Can you try w/ a history of 10,000 or at least 1025 entries?

Comment 51

[Brendan Eich [:brendan]]

Ouch!  Touching the DOM just sucks, performance-wise.  QuickSort and bubble-sort
do the same number of "assigns" (half-swaps, 0 and 224, respectively) when given
a 224-entry sorted and reversed list, so there should be no appreciable runtime
difference. But the essense of my "important(!) bugfix" was to save the pivot
state hanging under the lo-indexed element, even if you never ended up needing
it, every time.

Here comes a patch that defers saving the pivot state until we know we're about
to overwrite its attributes.  I hope it does better in both cases.

In the already sorted case, the next patch should make QuickSort perform about
the same as bubble-sort.  In the reversed case, there will be 112 "pivot saves",
which are akin to the temp = ... half of the swap code in the bubble-sort, but
via an array temporary (pivotValues) instead of in a local, temp, set during
each loop iteration.  There are 112 "pivot stores" too, having saved the silly
thing (we can't lose data!).  As bubble-sort has to do 112 swaps to sort a
reversed 224 element array, one would hope for about the same performance.

This all begs the question of what the *likely* input is, both in array length
and in order or disorder.  Isn't a nearly-sorted list likely for this particular
UI case?  I doubt a reversed list is, unless something tends to reverse the list
behind the user's back.

Not to beat a dead horse, but how about an RDF in-memory datasource approach?
How much work would that be?

/be

Comment 52

[Brendan Eich [:brendan]]

Attachment: QuickSort attempted that avoids all unnecessary DOM gets

Comment 53

[Stephen P. Morse]

Happy New Year!

Timing for brendan's next quicksort patch ("...avoids all unnecessary DOM gets")

   a. List already sorted:   1.2 seconds
   b. List sorted backwards: 2.2 seconds

> This all begs the question of what the *likely* input is, both in array
> length and in order or disorder.

The set of 224 sites was from a cookperm.txt file that someone had attached to 
some other bug report, so it was a real file.  If cookie manager and/or image 
manager are used, the user will quickly collect many sites in his cookperm list 
because that's the whole intent -- to build up a large repitoire of sites from 
which you do not cookies.

Since I'm not familiar with rdf, I have no idea how much work is involved to 
convert the cookie storage to an rdf datasource.  I didn't plan on doing so just 
to add a simple sort routine to the cookie manager dialog.  And the same would 
have to be done for password-manager storage as well.

Comment 54

[Stephen P. Morse]

I forgot to answer brendan's question about how much disorder to expect.  It 
could be quite common to get a list that is sorted in ascending order and it 
needs to be put in descending order (or vice versa).  I say that because it is 
what will happen if a user clicks on the same column heading twice in a row.  In 
fact, that's what made it so easy for me to run such a test and is why I have 
done that test in all the timing I reported.

Comment 55

[timeless]

When we know we are turning a list around, and in these views we do, we should 
use a function that does just that.

However we probably really should get all of these functions into the rdf 
backend instead.

Comment 56

[Brendan Eich [:brendan]]

Something doesn't compute (probably my patch attempts ;-): the quick.js and
bubble.js attachments have comparable runtime and identical complexity for the
ordered and reversed cases.  Unless there are still gratuitous DOM operations in
my last nsWalletTreeUtils.js attachment, it should not run much slower, if at
all slower, than the bubble-sort version.

Lest I waste everyone's time on what might be my bug, I'll try to get to the
bottom of this, but any help is appreciated.  Just counting "assignments" of DOM
attributes (id, value, ...) for each patch and dumping the tallies would help.
There should be 224 assignments or 112 swaps.

If the list can grow quite large, and may be unordered (neither forward nor
reverse ordered), then we do care about the difference between bubble-sort and
QuickSort.

We also should care about using existing mechanism, to keep footprint down (JS
footprint is all dynamic at runtime, but should be counted too when trading off
ad-hoc nsWalletTreeUtils.js code against alternatives).  Arguing for ad-hoc
bloat "just to add a simple sort routine" to a dialog doesn't move me, because
without rdf and other unified mechanism, all our dialogs that needed to sort
would have unacceptable bloat and redundancy.  Even a combination of finely
tuned ad-hoc sort methods could lead us astray if several such, with O(n**2)
growth as bubble-sort has, start to fall over in the field, on what could be
unexpectedly large/disordered inputs.

Alecf, how about some lxr pointers and advice on using an rdf datasource here?

/be

Comment 57

[Stephen P. Morse]

First off, I lied.  There are not 224 sites in my list, rather there are 226.

Below are the tallies the brendan requested.  They are identical for quicksort 
and bubblesort then thus don't give any clue as to why bubblesort is coming up 
faster.  However they do give me some ideas for making each implentation still 
faster -- namely:

1. Never use getAttribute for a value that is already being cached in the array.  
That will reduce the number of gets on the value attribute from 678 to 452.

2. Don't read value into the array untill it is first needed.  That will reduce 
the number of access in the already-sorted case to 0.

quicksort (already sorted)
--------------------------

   000: getting ID attribute
   000: setting ID attribute
   226: getting value attribute
   000: setting value attribute

quicksort (sorted backwords)
----------------------------

   226: getting ID attribute
   226: setting ID attribute
   678: getting value attribute
   452: setting value attribute

bubblesort (already sorted)
---------------------------

   000: getting ID attribute
   000: setting ID attribute
   226: getting value attribute
   000: setting value attribute

bubblesort (sorted backwards)
-----------------------------

   226: getting ID attribute
   226: setting ID attribute
   678: getting value attribute
   452: setting value attribute

Comment 58

[Stephen P. Morse]

Made the change to the bubblesort algorithm for using the value cache 
exclusively (item 1 in the comment above).  It had no significant effect on the 
timing although it did reduce the "getting value attributes" count to 452 as 
expected.

Attaching revised bubblesort patch.

Comment 59

[Stephen P. Morse]

Attachment: bubblesort optimized to better use the value-attribute cache

Comment 60

[Brendan Eich [:brendan]]

I hate a mystery: QuickSort version next attached avoids re-getting 'value'
(good one, DOM pain avoidance parity) and also avoids useless recursion.
QuickSort on a reversed list is especially painful without useless recursion
avoidance.

If this doesn't compete with bubble-sort for the reversed case, I have some
ideas for what to look at next.  The pivotValues array is one cost that
bubble-sort avoids by swapping as it traverses parallel nextSibling-linked
lists, but that QuickSort cannot avoid.  This cost shouldn't be too bad compared
to DOM operations, though.  None of the JS costs should rise above noise, as the
earlier quick.js and bubble.js xpcshell tests demonstrate.  Yet something seems
to be significantly costlier, from all morse's measurements.  A three-pipe
problem....

You cc'ers who are hip to RDF should school us, while we're having fun.

/be

Comment 61

[Brendan Eich [:brendan]]

Attachment: QuickSort version with getAttribute('value') and recursion minimization

Comment 62

[Stephen P. Morse]

Timing for latest quicksort patch ("...with getAttribute('value') and recursion 
minimization")

   a. List already sorted:   1.0 seconds
   b. List sorted backwards: 2.0 seconds

The count of getAttribute/setAttrbute calls is as follows:

quicksort (already sorted)
--------------------------

   000: getting ID attribute
   000: setting ID attribute
   226: getting value attribute
   000: setting value attribute

quicksort (sorted backwords)
----------------------------

   226: getting ID attribute
   226: setting ID attribute
   565: getting value attribute
   452: setting value attribute

Comment 63

[Stephen P. Morse]

Correction to above numbers for quicksort -- I was counting too many 
getAttribute's.

   a. List already sorted:   1.0 seconds
   b. List sorted backwards: 2.0 seconds

The count of getAttribute/setAttrbute calls is as follows:

quicksort (already sorted)
--------------------------

   000: getting ID attribute
   000: setting ID attribute
   226: getting value attribute
   000: setting value attribute

quicksort (sorted backwords)
----------------------------

   226: getting ID attribute
   226: setting ID attribute
   452: getting value attribute
   452: setting value attribute

Comment 64

[Stephen P. Morse]

Separating out the rdf issue into a new bug report (bug 65296) since that won't 
get done immediately.  Would like to keep the focus here on adding the sort to 
the existing data structure.

As best as I can tell, the status on this is that a super-review was requested 
from alecf and his response was:

   "looks ok to me, but I'd like to hear the final word from brendan.
    I've been trying to follow the history on this, but basically it
    sounds like we can't do a direct swap of nodes in the DOM tree
    itself, so we're swapping the "value" attribute instead? If someone
    can confirm that I've summarized this correctly, then sr=alecf"

Yes, I think you are summarizing it correctly.  So is the final word in on this 
yet?  Is there anything that I still need to do or should I consider the above 
as an sr=?

I'm referring now to the latest bubble-sort patch attached to this bug report 
because the timings that I have show that it is surprisingly faster than the 
latest quicksort patch that we have.

Comment 65

[Brendan Eich [:brendan]]

The next attachment is a QuickSort version that doesn't suffer from the high
cost of nested functions in JS (that cost is covered in bug 65308), which cost
accounts for the unexpected slowness of the previous QuickSort patches compared
to bubble-sort.

Average time for ten reverses of my 239-entry cookies.txt is 318.6ms. Average
time with bubblesort is 331.8ms, due to more getAttribute calls:

QuickSort reversing:
QuickSort time: 314, (id,value)x(get,set) = 230,230,465,460
QuickSort time: 320, (id,value)x(get,set) = 230,230,465,460
QuickSort time: 314, (id,value)x(get,set) = 230,230,465,460
QuickSort time: 315, (id,value)x(get,set) = 230,230,465,460
QuickSort time: 312, (id,value)x(get,set) = 230,230,465,460
QuickSort time: 313, (id,value)x(get,set) = 230,230,465,460
QuickSort time: 349, (id,value)x(get,set) = 230,230,465,460
QuickSort time: 319, (id,value)x(get,set) = 230,230,465,460
QuickSort time: 314, (id,value)x(get,set) = 230,230,465,460
QuickSort time: 316, (id,value)x(get,set) = 230,230,465,460

bubble-sort reversing:
bubble-sort time: 376, (id,value)x(get,set) = 292,292,535,584
bubble-sort time: 345, (id,value)x(get,set) = 286,286,529,572
bubble-sort time: 326, (id,value)x(get,set) = 292,292,535,584
bubble-sort time: 323, (id,value)x(get,set) = 286,286,529,572
bubble-sort time: 325, (id,value)x(get,set) = 292,292,535,584
bubble-sort time: 323, (id,value)x(get,set) = 286,286,529,572
bubble-sort time: 326, (id,value)x(get,set) = 292,292,535,584
bubble-sort time: 324, (id,value)x(get,set) = 286,286,529,572
bubble-sort time: 326, (id,value)x(get,set) = 292,292,535,584
bubble-sort time: 324, (id,value)x(get,set) = 286,286,529,572

But bubble-sort is simpler and smaller (in JS source and dynamic memory
footprint), and can beat QuickSort if QS pivots badly.

Cookie sorting could be even faster, with smaller brainprint and footprint, if
done by existing native NS_QuickSort code, but now that bug 65296 addresses the
long term (via RDF), the short-term JS-coded solution should go in (and if RDF
doesn't pan out, there's always Array.prototype.sort applied to a NodeList, bug
11115).  So sr=[e-mail] on the bubble-sort patch.

/be

Comment 66

[Brendan Eich [:brendan]]

Attachment: QuickSort without nested functions, to dodge bug 65308

Comment 67

[Stephen P. Morse]

Verifying brendan's new numbers.  The timing for the latest bubblesort and the 
latest quicksort are now very comparable.  It's practically a tie for the 
already-sorted case with the difference being less than the measurement error.  
I'm still seeing bubblesort being faster for the unsorted case, but by an 
insignificant amount.  These are the numbers I've seen for three runs each for 
the complete reversal case (times are in seconds):

   quicksort:  1.232, 1.262, 1.242
   bubblesort: 1.152, 1.162, 1.152

Agreeing with all brendan's comments and checking in the bubble-sort version.

Comment 68

[Terri Preston]

Verified fixed w98 build 2001080904