B4J Question List vs Map Lookup

[aaronk]

Hi,

I'm running into a performance issue in my B4J app.

At startup, I'm loading thousands of items into a List. Later, as the app runs, I send multiple FCM messages per second (typically 3–5 per second). Before sending each FCM message, I check whether a topic exists in the List using .IndexOf().

The problem is that over time, this check starts to slow things down significantly. The app begins to lag and struggle to keep up with the rate of messages. If I remove the check and send the FCM messages directly (without checking the List), everything runs smoothly without lag.

Out of curiosity, I asked ChatGPT for suggestions (as a guide only), and it pointed out that .IndexOf() on a List has linear time complexity (O(n)). So, with a large List, each lookup can be slow. It recommended using a Map instead, since lookups in those structures are generally O(1), making them much faster for this kind of check.

I understand ChatGPT isn't always perfect with coding advice, so I wanted to ask is it true that using a Map will give me better performance than a List for this use case?
Or is there another recommended way to check if a value exists in memory before processing the FCM message?

 

[Brian Dean]

Is the list fairly stable or are numbers being frequently added? If it is stable then I would sort it and use a binary search, but then I am an old-fashioned programmer. Adding and removing values from a sorted list is also quite quick. Searching an unsorted list is probably the least efficient procedure. Maps are reputed to be quick (and easy) but I have not seen figures that compare them to a binary search. Maybe checking that values are NOT present is different than checking that they are.

 

[emexes]

A map will give you massively better lookup performance.

 

[emexes]

List vs Map speed test results:

Comparing list and map speeds using 1000 items and lookups
Created list in 11 ms
Created map in 10 ms
Found 900 list entries in 8 ms
Found 900 map entries in 1 ms

Comparing list and map speeds using 10000 items and lookups
Created list in 6 ms
Created map in 30 ms
Found 9000 list entries in 468 ms
Found 9000 map entries in 4 ms

Comparing list and map speeds using 66000 items and lookups
Created list in 11 ms
Created map in 83 ms
Found 59400 list entries in 16089 ms
Found 59400 map entries in 16 ms

Comparing list and map speeds using 100000 items and lookups
Created list in 13 ms
Created map in 126 ms
Found 90000 list entries in 60203 ms
Found 90000 map entries in 23 ms

at n = 10000 map is about 100 times faster
at n = 100000 map is about 3000 times faster

 

[Brian Dean]

Maps are certainly fast. I have just run a quick (and not rigorous) test of your third case, using 66000 numbers and searches, with a sorted list and simple binary search. Maybe the binary search could be polished a bit, but my times were around 25msec compared with 16msec for a Map - not really close.

Edit : The 25msec figure was for numbers NOT in the list. If I restricted the searches to numbers that WERE in the list I could get times down to 17 or 18 msec.

 

[aaronk]

Is the list fairly stable or are numbers being frequently added?

Strings are constantly being added and removed, as well as being checked.

List vs Map speed test results:

Great, I should have done that test in a standalone app, I wasn't thinking at the time.

Based on your tests, looks like at start up it takes slightly longer to load the details in the map, but once loaded it's a lot faster.

In my B4J app, I have changed it from a list to a map, and sure enough (so far) its working much faster & better.

 

[Chris2]

If you don't need the values of the map, then it might be worth trying B4XSet too - https://www.b4x.com/android/forum/threads/b4x-b4xcollections-more-collections.101071/#content.

I haven't tested it but I imagine the lookup speed is similar to that of a map.

 

[MrKim]

Why not use SQLite? That is what databases are for: Looking things up quickly. Just index the lookup - and you can make it a pure memory DB. If you are checking if the message exists so you don't add duplicates make the field unique. Then you don't have to check. Just add it and let it fail if it exists.
Also, if you are loading the same data every time then you don't have to reload it. It will already be in the DB.

@emexes​

I am curious. If you give me the program that you used for testing I will add an SQLite DB to it and compare the results.

 

[aaronk]

I was originally doing it with a SQLite database a few years ago and my B4J app run slow in processing the queries as it couldn't keep up. To be fair I was doing everything in a large project and things couldn't keep up and I have since split up the project into smaller projects.

I then moved to MySQL and things started working quite well.

Then a few months later it started to lag again.

I then loaded it into a list and it fixed the issue for over a year. Now it's running slow.

I then moved from a list to a map and now it's really fast and currently working really well since.

 

[emexes]

I will add an SQLite DB to it and compare the results

Sounds great. My crystal ball forecasts that DB lookups will be faster than a List but slower than a Map.

 

[MrKim]

Sounds great. My crystal ball forecasts that DB lookups will be faster than a List but slower than a Map.

Your crystal ball was spot on MAPS WIN!
I first tried a regular SQLite table and to insert 66000 rows was ridiculously slow (126000 ms). So I switched to an in-memory table and it was slower to insert and slower for searches but acceptable. Just out of curiosity I upped it to 660000 records wondering if more records would give an advantage to the DB. It did not. At 660000 I commented out the list for the search as it was so ridiculously slow I lost patience and didn't wait for it to finish. There was no advantage for the DB with more data. There was a slight difference between Debug and compiled mode. Interestingly the list was slightly faster compiled and the map and DB slightly slower.

Comparing list and map speeds using 66000 items and lookups
Created list in 7 ms
Created map in 24 ms
Created Table in 559 ms
Found 59400 list entries in 5382 ms
Found 59400 map entries in 6 ms
Found 59400 Table entries in 573 ms

I was also curious about the actual issues so I logged the time to do each 5000 items. As expected since the items where searched in the same order they were created the list got progressively slower (ms):
5000 102
10000 179
15000 228
20000 296
25000 384
30000 446
35000 521
40000 604
45000 693
50000 597
55000 655
The map varied between 0 and 2 ms for 5000 (how do they do that!!!)
The SQLite table took between 42 and 66 ms to do 5000,
Both the map and SQL the times for 5000 were random not linear. Having more to do with allocated processor time than longer search time I imagine.

 

[Cableguy]

Why are maps faster than list?
In a list you can't search for a particular "keyword" but you search for the first entry containing a keyword...
So if in your list you have a keyword ="mykeyword1" and another ="mykeyword2", the .index Of will crawl the entire list until he finds the first occurrence of the keyword you are searc, while a map tests each letter, so it discards indexes much faster...
I hope I made sense, so...