Android: com.duckduckgo.app.entities.entityForUrl is slow

[ntoper]

I investigated the issues. It's simpler than I thought.

Methodology
I added a "real time tracker" instead of using Android Profiler (it's not very reliable).

Further Question
Also as it's a critical piece of the code maybe I should send a PR with the "slow query log". Do you want it?

Data
Here is an extract of some of my logs (time is in ms):

d.txt

You'll see some URL taking >500 ms to be "found'".

I think I know how to fix it. I'll work on it sometimes next week when I have a few hours for that. (And if someone else hasn't fixed it yet)

[subsymbolic]

Thanks for reporting this @ntoper. As for a PR yes please! As this is quite serious we have it scheduled internally too, although I don't imagine we'll look at it for another week or two. If we do we'll let you know to avoid duplicate effort.

[ntoper]

documenting as it goes (mostly in case someone takes over). I made sure the issue is with the DAO.

I logged access time of the only called method (UriString.sameOrSubdomain). Reported times are very very low and couldn't explain it.

[subsymbolic]

@ntoper thanks again for reporting this, we are now picking it up internally.

[dapacheco]

@subsymbolic I know that is now being fixed internally now, but my interest was piqued so I took a look at the problem.
I suspect you may have already found the same or better improvements, but on the off chance that this is still in the backlog here is what I found / tried.

I have identified two factors which cause the entityForUrl call to be slow:

• having to search at most 2374 items to find a matching entity for the url
• having to parse the url for each check in the find

To tackle the first problem I've filtered the entities list into a map keyed on the top level domain I've seen a big reduction in the time reported for calling the entityForUrl function.

Having wrapped the existing call with measureExecution I see the following difference between the existing call and a new call that uses the map

measure org https://data.cnn.com/jsonp/breaking_news/international.json?callback=CNNMarqueeCallback; took 777ms
measure map https://data.cnn.com/jsonp/breaking_news/international.json?callback=CNNMarqueeCallback; took 311ms

The second improvement was to only parse the child url once and not for each call to sameOrSubdomain

measure org https://data.cnn.com/jsonp/breaking_news/international.json?callback=CNNMarqueeCallback; took 435ms
measure map https://data.cnn.com/jsonp/breaking_news/international.json?callback=CNNMarqueeCallback; took 251ms

I've pushed my test here - https://github.com/duckduckgo/Android/compare/develop...dapacheco:issue/453?expand=1

[CDRussell]

Hi @dapacheco, thanks for profiling that and for the suggested change.

As you've observed, the list iteration is the worst offender here and it is something that is being changed. The map implementation is one thing we're considering, but we're also evaluating another idea which is to avoid pre-loading the entities altogether and doing a direct DB lookup when needed; this latter approach looks pretty promising in terms of decreasing the lookup times (and would also avoid calling sameOrSubdomain most likely).

So thanks for providing the map implementation and timings; that is useful to compare against the existing implementation and any others we try.

This poorly performing area, and a few others, are being actively worked on this week so expect some changes pretty soon in these code areas.

[subsymbolic]

This was fixed in https://github.com/duckduckgo/Android/pull/481. Thanks for reporting it!