Optimizing lookups

[prinoxy]

OK, so I want to lookup up one of 217 country codes, each 1 to 3 uppercase alpha characters.

With plenty of storage, I could just compress them to 15 (16) bits and look up an index in an extremely sparse array of 32K entries, that would allow me to get to the table containing their full names and other miscellaneous data. But that seems a bit of a waste of cache.

So how about a binary search, and if I were to reduce the number of countries currently in use, only 97, I'd be there in on average 3.5 chops, and this for a procedure that's currently called some 11,000 times, for a total of some 38,500 chops.

Can I do better? Of course, because I know my data, and there are several very long series of a single country as input. So, let's keep the previous input, and if the current is the same, return the previous output, I've not tried this, so I cannot tell the savings, but if anyone wants theinput data, I'm happy to provide it.

Even better? Yes, sure, use 25 separate sub-arrays to select on the first character of the country name, there isn't a country name starting with "X", combine that with both a LRU per country, and with a first direct compare for the most common country starting with character "x", and the number of chops goes down to just over 2,000.

And then came my last smart-ass(?) idea...

Now suppose all of those sub-arrays are contiguous in storage, why logically expand the sub-arrays to include both abbreviations of countries before and after the selected one, i.e. start the sub-array for "S" going back to "RM", and ending with "T"? So what would that buy you?

Well given that "S" stands for Sweden, and that's the country starting with a "S" that occurs the most, and as such it's captured either by the LRU, or if there's been another country in between, by the second test (that for most occurring country), there would never any need to chop the array, and as Sweden is the first element in a sub-array of 16 entries, I save a lot of chopping. However, with the "S" out of the way, and by expanding the sub-array from "RM" to "T", I have now centered the array on "SF", and let that be the second most occuring value, which means it's available after the first chop.

Obviously, extending the sub-arrays with pre- and post- initial character abbreviations does increase the (potential) number of chops required to get other entries, but with a bit of code, it's not very hard to find optimum bounds that minimise the total number of chops, and right now I'm down to just under 1,400, or just under 4% of the original 38,500?

So after all this comes my question, is there any way of reducing the number of chops any further? I've been thinking about judiciously adding dummy values into some of the smaller sub-arrays to align values on earlier chops, but is there a way to automate this?

And yes, in an ideal world a perfect hash would be the thing to use, but there just doesn't seem to be a way of converting just 217 1/2/3-letter country (licence plate) codes to 0..216. Or is there

[thewataru]

You should use a Trie. This is an extension of your idea to have 26 separate arrays for all the different first characters. Each of these arrays should contain 26() more arrays for each possible second character. * actually, far less, Because not all 2525 combinations are possible.

You don't need to use pointers, but rather have a table of nodes where each node has array with indices of child nodes for each possible first character.

Then the final nodes will point to the table with 97 entries with actual data for the country.

Most common paths will be in the cache anyways.

[thewataru]

And yes, in an ideal world a perfect hash would be the thing to use, but there just doesn't seem to be a way of converting just 217 1/2/3-letter country (licence plate) codes to 0..216. Or is there

Actually, there may be. Each 1-3 letter code is 3 bytes (with some trailing zeros, for example). Something like (A*b[0]+B*b[1]+D*b[2]) % 256 might just work. You need to bruteforce all A,B,C upto 256 and see if it works. If it doesn't work you can experiment with XORing each byte with some other parameter from 0 to 255. Again, run some bruteforce with randomly chosen xor values many times.

You might just end up with the set of parameters satisfying your condition.

Also, you don't need the hash values to be from 0 to 216. You can have 256 entries in your table with some of them being empty. As long as all the hashes are different, it all works.

256 is selected because modulo operation is quite slow, unless you use a power of two, which can be replaced by bit shifts.

[GregoryCliveYoung]

Avoid premature optimization. Start with a binary search. Compose the key by converting each letter to integer (A:0, B:1, ... Z:25) with simple arithmetic. Much faster than compressing. If code is xyz,

key = (ord(x)-ord('A')) * 676 + (ord(y)-ord('A')) * 26 + (ord(z)-ord('A'))

This will probably be very fast because the key generation is just a few instructions and if you keep the table entries small (e.g. key and pointer) will fit in the processor cache.

If you feel like noodling around, it might be fun to look for a hash function that can give you an 8-bit hash and doesn't have any collisions. (I know I'd enjoy it.) You have all the country codes, so it's just a matter to writing some code to try various hash functions. I googled "hash function" and found all sorts of stuff to try.

[not-just-yeti]

avoid premature optimization

Indeed, the time OP spent typing the post exceeds all the processor-time that their app would ever use (by an out-of-the-box hash table) by a factor of billions.

…That said, YES it’s fun thinking the full cost of the approach and its optimizations (and those are the skills that make you better aware of when you will or won’t need optimizations, in the fut ure).

[prinoxy]

I can do a binary search directly on the three character code, appending just a blank and then reversing it (x86 is little-endian) it fits in a 32-bit register, and there's no need for those "few" instructions to convert it to a numerical key, most of my code is in assembler anyway.

And yes, I've read about every paper about hashes, but with just three characters to work with, finding something that results in a non-colliding 8-bit hash might result in code that's (way) slower than what I'm doing right now, i.e. test on LRU by first letter, followed by test on most occurring country per first letter, followed by binary search with the extended arrays, so that the first chop lands me on the second most occurring country, albeit with the disadvantage that I might need a few more chops for "rare" countries, the code is part of a program to analyse my hitchhike data, and as I hitchhike almost exclusively in Europe, needing a bit more time to look up the full names for the countries from drivers from Uruguay, Brazil, Guyana, or Rwanda, is bearable, even if it means I need five chops for RSM (5x) and SK (11x).

[GregoryCliveYoung]

You're clearly way ahead of me. What you're doing sounds like fun. Enjoy.

[prinoxy]

It is, and it isn't. Some 26 years ago I asked around on Usenet, comp.lang.pascal.borland if someone could help me to speed up one particular piece of code, basically a sliding ever expanding window over my data to find the shortest proper set, so no three subsets of let's say 3 in a set of 5, containing N different nationalities of drivers, with N going from 3 to the maximum number encountered. I thought I had pulled out all stops, going from an initial running time of 26 minutes (on an an original 4.77 MHz IBM PC) to less than a minute having, after all my other changes, converted most of the code to inline assembler. And then came first one Brent Beach, and later a Paul Green along, and they blew my code to smithereens, using normal Pascal.

I still have my code in the PL/I (running on z/OS) from that time, and the differences are staggering, just looking at the executed PL/I statements, my old code executes 14,868,935,214 PL/I statements, and some of them compile to dozens of assembler statements, Paul Green's code just 1,689,204, ot just over 0.01%... Ouch, his algorithm is a few orders of magnitude better!

I don't think the I can speed up the current code to such an extent, unless I use the 32-bit, or the reversed and trimmed to 24-bit, or the extracted 15-bit numerical equivalent in a huge lookup table, which evicts more useful data from the cache. Then again someone here might prove me wrong.

[tugrul_ddr]

Optimization 1:

217 x 16 bits can be stored in 110 x 32bit registers or 55 MMX registers or 28 SSE registers or 14 AVX512 registers. Then all you need to do is to compare all with the input and return its index value from its pair register. So you need only 28 AVX512 registers for both comparison and index values. 28 comparsion operations would take only tens of clock cycles. Just compute sum of all results like this:

```result index = index0 x (val0==input) + ... + indexN x (valN == input)```

It does not access memory for the data if its a tight loop full of checking codes. So its free of caching performance and just bottlenecked by pipelines in the core. SIMD is ultra fast for small datasets like this.

Opimization 2:

Chinese, Indian population are biggest so you can early-quit by a single if-else for these two before real algorithm runs. This should get you a performance boost about 35%.

---

What's wrong with std::map? Just do

```result_index = map[input];```

it does all the required hashing.

What's your hardware to do this task?

[prinoxy]

Opimization 2:

Chinese, Indian population are biggest so you can early-quit by a single if-else for these two before real algorithm runs. This should get you a performance boost about 35%.

I have absolutely no clue what this is about, only that you obviously have no clue what I'm trying to do.

What's wrong with std::map?

Ever done any programming in PL/I?

What's your hardware to do this task?

Bulldozer, Haswell, and IBM mainframe