943081 - Follow-up: more efficient implementation of isDefaultIconPage

Status: RESOLVED FIXED

(Firefox for Android Graveyard :: General, defect)

Comment 1

[raymond [:retornam] (inactive)]

Hi R Newman,
Can you please provide more information about this bug. I'd like to work on this, thanks

Comment 2

[Richard Newman [:rnewman]]

See mobile/android/base/AboutPages.java. `isDefaultIconPage` returns true if a page is in DEFAULT_ICON_PAGES. It does so through complete string equality and iteration.

We can almost certainly make that quicker. This bug is to do so, measuring first to determine how much.

Comment 3

[Vlad Tanase]

Hi,

I have had a look at this today, and tried a couple of options without much success. Could you please be more specific as to what exactly you had in mind with this optimisation?

I created a test harness (http://pastebin.mozilla.org/4328412) that generates urls using the UUID class and runs both the old and new implementation on the same data. I used sets of 100000 urls, over 100 runs to get min, max and avg execution times. These are all worst case scenarios performance wise, since we will always go through the full array of constants without getting a hit.

Using this setup I tried the following:
* concatenate all the constants into a single String and lookup the URL using indexOf
* using a HashSet for the constants and calling contains to get O(1) for the lookup instead of O(n)
* checking the hashCodes of the Strings before doing the equals call
* used substring on the url, to compare without the "about:" part
* implemented my own equals function to only check from the 6th char onward, to avoid the eventual overhead of creating a new String
but none of them provided better performance. Is there some other way that I am missing? Did you have something specific in mind for this?

Comment 4

[Michael Comella (:mcomella) [NI reported issues only: ex-Mozilla]]

(Drive-by comment, take rnewman's advice as definitive. Richard, feel free to contradict me. :)

Going completely on theory, I'm in favor of the HashSet - O(1) lookup. We can also get rid of the !url.startsWith("about:") to save some more cycles. Additionally, since we're already storing `DEFAULT_ICON_PAGES` in memory, the only use of it is in `getDefaultIconPages`, which is only called by something that just iterates over it (Set has a .iterator method), we can replace that String[] with this HashSet for nearly the same memory use, depending on the HashSet implementation. Wrap that in `Collections.unmodifiableSet` and we have a safety win (given that we don't mind the additional memory use).

However, that being said, benchmarks are often more important than theory, particularly when these data structures are quite small. Can you attach the program output so we can see? Also, there are some things to consider:
  * Running this on desktop is different than running this on devices, and running this on powerful devices is different than running this on less powerful devices. It might be nice to get these benchmarks on several devices
  * We want to avoid allocating GC'd objects on mobile (we should probably look into the HashSet implementation to ensure that it avoids allocation! If it's bad, we may want to use another method). Additionally, keep in mind System.gc is only a recommendation, not an absolute [1] so I'm not sure what effects it has on the benchmark (i.e. I'd take it out)
  * Running these tests in targetted benchmarks is different than running it practice (e.g. benchmarks fill up the CPU cache (and this discrepency is probably hidden by averaging the 100 runs) but having this method called once per page load should not take advantage of the cache)
  * This improvement is called once per page load and will likely be insignificant compared to layout - we are expecting minimal gains

[1]: https://developer.android.com/reference/java/lang/System.html#gc%28%29

Comment 5

[Richard Newman [:rnewman]]

Half of the work in this bug is just determining whether the current implementation is slow, particularly for about: URIs. If it isn't, great!

You should probably do so in an Android test. Desktop Hotspot will ruin your benchmark.



(In reply to Michael Comella (:mcomella) from comment #4)
> We can also get rid of the !url.startsWith("about:") to save some more cycles.

Au contraire. For most of the URLs you visit, this'll turn into a super-cheap shortcut -- "http://...." will be a different length and won't start with 'a'.

(The fastest implementation of this function for 99% of URIs would begin "is this URI about:home, or is it not an about: URI at all?". Which is kinda what I did, so this bug might be a WORKSFORME.)


> ... we can
> replace that String[] with this HashSet for nearly the same memory use,
> depending on the HashSet implementation.

The question here is whether it's cheaper to hash a string and do a lookup in a 10-element HashSet, versus doing a linear search using string equality.

String equality is fast, and we only get to this part of the code if we have an about: URI, so we're very likely to find a match (because most about: patches have default icons). So we're talking about ~5 string comparisons of short strings, versus a hashing and a tree lookup, probably with a check-equality at the end...

My intuition is that a linear search is cheaper. This bug is probably going to go in the direction of "is there a cheaper linear search" -- for example, can we compare strings in reverse, which avoids the about: check?

Comment 6

[Vlad Tanase]

After a long time tinkering with all the mostly undocumented things, I was finally able to run the performance test on an Android emulator.

These are the results I got:
> I/TestRunner( 2277): started: testIsDefaultIconPage(org.mozilla.gecko.background.common.TestAboutPages)
> I/System.out( 2277): Old took (avg): 579ms
> I/System.out( 2277): Set took (avg): 446ms
> I/System.out( 2277): Alt eq took (avg): 415ms
> I/TestRunner( 2277): finished: testIsDefaultIconPage(org.mozilla.gecko.background.common.TestAboutPages)
> I/TestRunner( 2277): passed: testIsDefaultIconPage(org.mozilla.gecko.background.common.TestAboutPages)

It seems to be that comparing Strings in reverse actually provides better performance but the set implementation comes pretty close as well. I have attached a patch with what I used for testing.

rnewman, could you tell me if the improvements we are seeing are worth going after? If so which solution would be best? In my opinion even though the set version is slightly slower it produces more maintainable code than rolling up our own String equality method.

If we want to make these changes, I'll try and provide a proper patch with the modified method asap.

P.S.: dealing with Proguard and the way to run the tests from background-junit3.apk should really be included into this page: https://wiki.mozilla.org/Mobile/Fennec/Android, the lack of documentation made this issue way more frustrating than it should have been.

Comment 7

[Vlad Tanase]

Attachment: Patch with tests used for performance comparison

Comment 8

[Richard Newman [:rnewman]]

(In reply to Vlad Tanase from comment #6)

> After a long time tinkering with all the mostly undocumented things, I was
> finally able to run the performance test on an Android emulator.

Thanks for doing all of this legwork!

Was this an x86 emulator or an ARM emulator?


> > I/System.out( 2277): Old took (avg): 579ms
> > I/System.out( 2277): Set took (avg): 446ms
> > I/System.out( 2277): Alt eq took (avg): 415ms

OK, so for 100,000 runs we're saving 164ms.

If this is on an x86 emulator (much faster than device), then this might be worth pursuing: a device would be much slower. If this is the case then I'll run these tests on a device and get a 'live' measurement.

If this is on an ARM emulator (much slower than device), then this probably isn't worth pursuing.


> P.S.: dealing with Proguard and the way to run the tests from
> background-junit3.apk should really be included into this page:
> https://wiki.mozilla.org/Mobile/Fennec/Android, the lack of documentation
> made this issue way more frustrating than it should have been.

The JUnit3 tests are brand new and not documented yet -- kudos for figuring them out!

Comment 9

[Vlad Tanase]

(In reply to Richard Newman [:rnewman] from comment #8)

> 
> Was this an x86 emulator or an ARM emulator?
> 
I used an ARM emulator for the tests. So what would be the next step for this? Will you run the tests on an x86 device and decide based on those?

Comment 10

[Richard Newman [:rnewman]]

(In reply to Vlad Tanase from comment #9)

> I used an ARM emulator for the tests. So what would be the next step for
> this? Will you run the tests on an x86 device and decide based on those?

Yes. I hope to get to this today.

Comment 11

[Richard Newman [:rnewman]]

On my x86 device:

 Old took (avg): 91ms
 Set took (avg): 116ms
 Alt eq took (avg): 119ms

Huge props for putting this together and writing the test, but it looks like this is as fast as it's gonna get.

I'm going to resolve this as FIXED, because there's no further work to do. I'd be delighted to mentor you through one of our other outstanding bugs, if you're in the mood for a meatier challenge; you certainly seem to have the aptitude.