202131 - BubbleSort is too slow

Status: RESOLVED FIXED

(Core :: Networking: Cookies, defect)

Description

[[e-mail]]

Comment 1

[[e-mail]]

Attachment: Proposed patch

Comment 2

[[e-mail]]

-> neil, though if you don't want it, feel free to kick it to mvl ;)

Comment 3

[Roland Mainz]

Just curious:
Does the JS "standard" not define something like |qsort()| ?

Comment 4

[Darin Fisher]

Comment on attachment 120583 [details] [diff] [review]
Proposed patch

>+  var compareFunc = function compare(first, second) {
>+    if (first[column] < second[column])
>+      return ascending ? 1 : -1;
>+    else if (first[column] > second[column])
>+      return ascending ? -1 : 1;
>+    else
>+      return 0;
>+  }
>+  table.sort(comareFunc);

oops!

    table.sort(compareFunc);

also, in the if-else block "else after return is non sequitur."

    if (...)
      return ...;
    if (...)
      return ...;

Comment 5

[[e-mail]]

mvl: if you get bored on a rainy day, any chance of benchmarking this to see how
much we win?

Comment 6

[[e-mail]]

Attachment: Fixed patch

Comment 7

[[e-mail]]

would it be worth it to shift the |ascending| check outside the compareFunc so
we don't check it on every iteration? like

+  if (ascending) {
+    var compareFunc = function compare(first, second) {
+      if (first[column] < second[column])
+        return 1;
+      if (first[column] > second[column])
+        return -1;
+      return 0;
+    }
+  else {
+    var compareFunc = function compare(first, second) {
+      if (first[column] < second[column])
+        return -1;
+      if (first[column] > second[column])
+        return 1;
+      return 0;
+    }
+  }
+  table.sort(compareFunc);

although the scoping may be wrong (i'm not familiar with js...)

Comment 8

[Christian :Biesinger (don't email me, ping me on IRC)]

>Does the JS "standard" not define something like |qsort()| ?

It defines Array.sort (which Mozilla implements using Heapsort), which is what
this patch uses.

Comment 9

[Darin Fisher]

biesi: what's wrong with heapsort?

Comment 10

[Boris Zbarsky [:bzbarsky]]

+    var compareFunc = function compare(first, second) {
+      if (first[column] < second[column])
+        return 1;
+      if (first[column] > second[column])
+        return -1;
+      return 0;
+    }

How about:

var compareFunc = function compare(first, second) {
   return second[column] - first[column];
}

?  That may even be faster...

Comment 11

[Christian :Biesinger (don't email me, ping me on IRC)]

Darin: Oh, nothing. I didn't mean to imply that.

Comment 12

[Michiel van Leeuwen (email: mvl+moz@)]

I tested this suggestions using a 2000 lines cookperm.txt and with measuring the
time spend in PermissionColumnSort() (called from loadPermissions).

Current trunk:   5294 ms
Neils patch:      493 ms
dwittes version:  468 ms

This are not real scientific tests (only one, not very representative sample),
but it shows that is is a huge improvment. 

bz: your version doesn't work. It just sorts on some random way (and is very
fast :) )

Comment 13

[[e-mail]]

we're talking about sorting strings here, right?

so i guess operator- isn't defined. feel free to write one bz :)

i really can't believe we got such a huge improvement. i remember seeing a
lengthy & involved discussion in a bug somewhere, on the sorting function we
currently use: so i would've guessed we'd have something "good". ;)

so Neil, what do you want for christmas?

Comment 14

[Michiel van Leeuwen (email: mvl+moz@)]

More testing with 150 entries:

Current trunk:   64 ms
Neils patch:     67 ms
dwittes version: 66 ms

The differences could very well be just noise. And if it isn't it, nobody will
notice it. But the improvment for many entires surely is visible.

Comment 15

[[e-mail]]

ah that explains my previous comment then. when the current algo was chosen, the
tests were made using ~250 entries iirc... which kinda ignores the fact that
this algo is also used for sorting permissions (which are unlimited, some folks
have >10,000)...

Comment 16

[Michiel van Leeuwen (email: mvl+moz@)]

For fun, tested a nsVoidArray::Sort() method. (directly from nsPermissionManager)
We can't use that directly here, but is good te remember for the future. We
might use it on day.

PR_STATIC_CALLBACK(int) comparePermissionsByHost(const void* entry1, const void*
entry1, void *aData)
{
  return strcmp(((const nsHostEntry*) entry1)->GetKey(), ((const nsHostEntry*)
entry1)->GetKey());
}

hostList->Sort(comparePermissionsByHost, nsnull);


takes about 2000 usec, while the same list takes 500 msec in javascript (2000
entries) The list passed to JS is already sorted.

Comment 17

[[e-mail]]

christmas presents all around.

using the nsVoidArray::Sort approach would require reworking our ifaces so
wallet can pass in a |sortBy| parameter to the backend. this isn't unreasonable
for such a big speed gain, but such stuff can probably wait for more thorough
wallet work, and this JS stuff is acceptably fast for now, imo...

if darin/bz agree, somebody post a patch and let's get this in :)

Comment 18

[[e-mail]]

Attachment: slightly quicker patch

this one is the same as Neil's patch but with the two separate comparison
functions depending on |ascending|.

Comment 19

[[e-mail]]

Comment on attachment 120641 [details] [diff] [review]
slightly quicker patch

darin - does this look ok? if you'd prefer the single comparison function with
the |ascending| inside then feel free to sr neil's patch.

Comment 20

[Darin Fisher]

Comment on attachment 120641 [details] [diff] [review]
slightly quicker patch

fine by me.  though i'm surprised javascript has no equivalent of strcmp.

Comment 21

[[e-mail]]

it most likely does, but this comparator is used for ints and string and other
sundry whatnots. so we just let js mangle them into whatever it sees fit ;)

so yes, if we used a C-based comparator with nsVoidArray::Sort we'd need
probably 2 comparators, one for strings and one for ints.

Comment 22

[Darin Fisher]

ok :-)

Comment 23

[Boris Zbarsky [:bzbarsky]]

Oh, we're sorting strings?  I didn't realize that '<' and '>' worked on strings
in JS... ;)  (my version would treat all the strings as 0 and sort the
numbers... ;) )

One other item of curiousity... what happens if you just call sort() with no
args and then call reverse() if needed?  I doubt this will help anything much,
since I'd hope that JS func invocations is not that much slower than calling the
default sort C func, especially when the time to reverse() is taken into account...

Comment 24

[[e-mail]]

heh, > and < even work on nsAString/nsACString iirc, although i would strongly
lean toward strcmp for such applications :)

i didn't quite grok your second paragraph though - you mean just have one
comparator func indpendent of |ascending|, and then reverse() after the sort if
|!ascending| or something like that?

Comment 25

[Boris Zbarsky [:bzbarsky]]

> you mean just have one comparator func indpendent of |ascending|, and then
> reverse() after the sort

Yes.  Except the comparator func you would use would be the one hardcoded in C
in the JS engine; you wouldn't be passing in the func.  So the code would look like:

array.sort();
if (!ascending) {
  array.reverse();
}

This would make sure to mangle all array entries into strings and sort them in
lexicographic order (note that this is not quite equivalent to your code if some
of the entries are numbers; eg "20, and "11" will sort differently....)


(if this happens to be worth doing it would need a nice comment explaining why
it's done that way, of course).

Comment 26

[[e-mail]]

ah, i see. but how would you write that for a "tree"? (i hate that term, but
what we have here is an array with several "columns", notice the comparator
function picks out the column passed in as a global).

i tried a couple of permutations:
tree[column].sort(), which obviously won't work, and
tree.sort()[column] which actually ran but didn't do anything very useful :)

is there a cunning way to denote the element to sort by, without using custom
comparators like we do now?

Comment 27

[Boris Zbarsky [:bzbarsky]]

Oh, duh.  Never mind me... I should read more carefully.  :(

Comment 28

[[e-mail]]

Attachment: Patch using .reverse()

Comment 29

[Michiel van Leeuwen (email: mvl+moz@)]

Comment on attachment 120641 [details] [diff] [review]
slightly quicker patch

Let's go for it

Comment 30

[Christian :Biesinger (don't email me, ping me on IRC)]

Checking in nsWalletTreeUtils.js;
/cvsroot/mozilla/extensions/wallet/cookieviewer/nsWalletTreeUtils.js,v  <-- 
nsWalletTreeUtils.js
new revision: 1.6; previous revision: 1.5
done

Comment 31

[Sander]

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

Comment 32

[[e-mail]]

Attachment: omission in checkin

argh, I missed this in the patch... Neil had it in his version of the patch,
and I thought i'd included it. thanks for pointing it out Neil.

Comment 33

[[e-mail]]

Comment on attachment 122109 [details] [diff] [review]
omission in checkin

r=dwitte since this was Neil's fix.

Comment 34

[[e-mail]]

Comment on attachment 122109 [details] [diff] [review]
omission in checkin

can i get a quick review here? ;)

simply put, the old code (it's been there for ages) is wrong.

Comment 35

[[e-mail]]

bleh. by 'quick' i meant it would _be_ quick. not that i'm asking for it quickly. ;)

Comment 36

[Darin Fisher]

Comment on attachment 122109 [details] [diff] [review]
omission in checkin

sr=darin

Comment 37

[[e-mail]]

Comment on attachment 122109 [details] [diff] [review]
omission in checkin

requesting approval to check in this trivial  one-line omission from a previous
patch.

Comment 38

[(not reading, please use [e-mail] instead)]

Comment on attachment 122109 [details] [diff] [review]
omission in checkin

a=sspitzer

Comment 39

[[e-mail]]

patch checked in.