4

I'd like to do a lookup mapping 32bit integer => 32bit integer.

The input keys aren't necessary contiguous nor cover 2^32 -1 (nor do I want this in-memory to consume that much space!).

The use case is for a poker evaluator, so doing a lookup must be as fast as possible. Perfect hashing would be nice, but that might be a bit out of scope.

I feel like the answer is some kind of cython solution, but I'm not sure about the underpinnings of cython and if it really does any good with Python's dict() type. Of course a flat array with just a simple offset jump would be super fast, but then I'm allocating 2^32 - 1 places in memory for the table, which I don't want.

Any tips / strategies? Absolute speed with minimal memory footprint is the goal.

Improve this question
5
  • 1
    "Absolute speed with minimal memory": you do know that there is not an optimal choice here, yes? It requires a satisficing engineering trade-off that yields (by definition) one or two sub-optimal choices. If Ignacio's answer is too memory intensive then module sqlite3 is probably your best simple alternative. Commented Jul 21, 2014 at 4:59
  • Do you know how many entries your mapping will have, and are you willing to sacrifice initial creation time to make lookups faster? Commented Jul 21, 2014 at 5:23
  • Also, what does "absolute speed" mean to you? Total CPU cycles consumed over the entire lifetime of the table (including creation time), or just the cycles spent doing lookups? Commented Jul 21, 2014 at 5:25
  • @NickBastin: initial creation time is not an issue, only time done doing lookups. the table could have 133 million entries at most. Commented Jul 21, 2014 at 16:36
  • If your bottleneck is going to be int→int mappings, you should use PyPy and use the standard PyPy dict. PyPy is so absurdly fast for this use-case it isn't even funny. Commented Oct 1, 2014 at 21:19

3 Answers 3

Reset to default
6

You aren't smart enough to write something faster than dict. Don't feel bad; 99.99999% of the people on the planet aren't. Use a dict.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

if it helps, the key space once initialized is completely static - no insertions needed.
Doesn't change a thing.
It's really not that hard to write something faster than the standard dict for many very specific use cases - even to the point of just taking the dict implementation itself and optimizing it and exposing it as a new object. dict is fantastic and reasonably optimal for the general use case, but that means there are tradeoffs that punish almost every specific use (possibly with the exception of general string hashing, which dict is very good at).
4

First, you should actually define what "fast enough" means to you, before you do anything else. You can always make something faster, so you need to set a target so you don't go insane. It is perfectly reasonable for this target to be dual-headed - say something like "Mapping lookups must execute in these parameters (min/max/mean), and when/if we hit those numbers we're willing to spend X more development hours to optimize even further, but then we'll stop."

Second, the very first thing you should do to make this faster is to copy the code in Objects/dictobject.c in the Cpython source tree (make something new like intdict.c or something) and then modify it so that the keys are not python objects. Chasing after a better hash function will not likely be a good use of your time for integers, but eliminating INCREF/DECREF and PyObject_RichCompareBool calls for your keys will be a huge win. Since you're not deleting keys you could also elide any checks for dummy values (which exist to preserve the collision traversal for deleted entries), although it's possible that you'll get most of that win for free simply by having better branch prediction for your new object.

Improve this answer

2 Comments

Do you mean the cython source? at https://github.com/cython/cython? I can't seem to find the Objects/dictobject.c file there, even with search...
The "cpython" source - the source code for python itself (the C implementation). You can start with the default dict object and just tweak it to make it faster.
4

You are describing a perfect use case for a hash indexed collection. You are also describing a perfect scenario for the strategy of write it first, optimise it second.

So start with the Python dict. It's fast and it absolutely will do the job you need.

Then benchmark it. Figure out how fast it needs to go, and how near you are. Then 3 choices.

  1. It's fast enough. You're done.
  2. It's nearly fast enough, say within about a factor of two. Write your own hash indexing, paying attention to the hash function and the collision strategy.
  3. It's much too slow. You're dead. There is nothing simple that will give you a 10x or 100x improvement. At least you didn't waste any time on a better hash index.
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.