Large Dictionaries

[Chris Foote]

Hi all.

I have the need to store a large (10M) number of keys in a hash table,
based on a tuple of (long_integer, integer). The standard python
dictionary works well for small numbers of keys, but starts to
perform badly for me inserting roughly 5M keys:

# keys dictionary metakit (both using psyco)
------ ---------- -------
1M 8.8s 22.2s
2M 24.0s 43.7s
5M 115.3s 105.4s

Has anyone written a fast hash module which is more optimal for
large datasets ?

p.s. Disk-based DBs are out of the question because most
key lookups will result in a miss, and lookup time is
critical for this application.

Cheers,
Chris

[Richie Hindle]

[Chris]

Has anyone written a fast hash module which is more optimal for
large datasets ?

PyJudy might be what you're looking for, though I've never used it:

http://www.dalkescientific.com/Python/PyJudy.html

"Judy's key benefits are scalability, high performance, and memory
efficiency. A Judy array is extensible and can scale up to a very large
number of elements, bounded only by machine memory." ... "PyJudy arrays
are similar to Python dictionaries and sets."

--
Richie Hindle
ri****@entrian. com

[Roy Smith]

In article <1147699064.107 490@teuthos>, Chris Foote <ch***@foote.co m.au>
wrote:

Hi all.

I have the need to store a large (10M) number of keys in a hash table,
based on a tuple of (long_integer, integer). The standard python
dictionary works well for small numbers of keys, but starts to
perform badly for me inserting roughly 5M keys:

# keys dictionary metakit (both using psyco)
------ ---------- -------
1M 8.8s 22.2s
2M 24.0s 43.7s
5M 115.3s 105.4s

Are those clock times or CPU times?

How much memory is your process using and how much is available on your
machine?

I'm guessing a integer takes 4 bytes and a long integer takes roughly one
byte per two decimal digits. Plus a few more bytes to bundle them up into
a tuple. You've probably got something like 20 bytes per key, so 5M of
them is 100 meg just for the keys.

To get reasonable hashing performance, the hash table needs to be maybe
half full, and figure a hash key is 4 bytes, so that's another 40 meg for
the hash table itself.

Plus whatever the values stored in the dictionary take up. Even if you're
not storing any values (i.e., there's probably 4 bytes for a null pointer
(or reference to None), so that's another 40 meg.

These are all vague guesses, based on what I think are probably
conservative estimates of what various objects must take up in memory, but
you see where this is going. We're already up to 180 meg. I wonder if the
whole problem is that you're just paging yourself to death. A few minutes
watching your system memory performance with ps or top while your program
is running might give you some idea if this is the case.

[Claudio Grondi]

Chris Foote wrote:

Hi all.

I have the need to store a large (10M) number of keys in a hash table,
based on a tuple of (long_integer, integer). The standard python
dictionary works well for small numbers of keys, but starts to
perform badly for me inserting roughly 5M keys:

# keys dictionary metakit (both using psyco)
------ ---------- -------
1M 8.8s 22.2s
2M 24.0s 43.7s
5M 115.3s 105.4s

Has anyone written a fast hash module which is more optimal for
large datasets ?

p.s. Disk-based DBs are out of the question because most
key lookups will result in a miss, and lookup time is
critical for this application.

Cheers,
Chris

Python Bindings (\Python24\Lib\ bsddb vers. 4.3.0) and the DLL for
BerkeleyDB (\Python24\DLLs \_bsddb.pyd vers. 4.2.52) are included in the
standard Python 2.4 distribution.

"Berkeley DB was 20 times faster than other databases. It has the
operational speed of a main memory database, the startup and shut down
speed of a disk-resident database, and does not have the overhead of
a client-server inter-process communication."
Ray Van Tassle, Senior Staff Engineer, Motorola

Please let me/us know if it is what you are looking for.

Claudio

[Aahz]

In article <ro************ ***********@rea der1.panix.com> ,
Roy Smith <ro*@panix.co m> wrote:

In article <1147699064.107 490@teuthos>, Chris Foote <ch***@foote.co m.au>
wrote:

I have the need to store a large (10M) number of keys in a hash table,
based on a tuple of (long_integer, integer). The standard python
dictionary works well for small numbers of keys, but starts to
perform badly for me inserting roughly 5M keys:

# keys dictionary metakit (both using psyco)
------ ---------- -------
1M 8.8s 22.2s
2M 24.0s 43.7s
5M 115.3s 105.4s

Are those clock times or CPU times?

And what are these times measuring? Don't forget that adding keys
requires resizing the dict, which is a moderately expensive operation.
Once the dict is constructed, lookup times should be quite good.
--
Aahz (aa**@pythoncra ft.com) <*> http://www.pythoncraft.com/

"I saw `cout' being shifted "Hello world" times to the left and stopped
right there." --Steve Gonedes

[Roy Smith]

Aahz <aa**@pythoncra ft.com> wrote:

Don't forget that adding keys requires resizing the dict, which is a
moderately expensive operation.

My guess would be that each resize grows the table by a constant
factor, which IIRC, works out to amortized O(n). It's not as good as
creating the dict the right size in the first place, but it's really
not that bad. Somewhat more troubling is that it can lead to memory
fragmentation problems.

I don't understand why Python doesn't have a way to give a size hint
when creating a dict. It seems so obvious to be able to say "d = dict
(size=10*1000*1 000)" if you know beforehand that's how many keys
you're going to add.

Looking at the docs, I'm astounded to discover that you can indeed do
exactly that, but you get {size:10000000} . I am befuddled as to why
people thought creating a dict by keyword would be a useful thing to
do, but left out (and, indeed, eliminated the chance to add the syntax
later) the obviously useful ability to hint at the size. I suppose we
could still add:

d = {}
d.reserve (10*1000*1000)

[Maric Michaud]

Le Lundi 15 Mai 2006 19:24, Roy Smith a écrit*:

d = {}
d.reserve (10*1000*1000)

d={}.fromkeys(x range(5*10**6)) ?

--
_____________

Maric Michaud
_____________

Aristote - www.aristote.info
3 place des tapis
69004 Lyon
Tel: [phone]

[Paul McGuire]

"Claudio Grondi" <cl************ @freenet.de> wrote in message
news:e4******** **@newsreader3. netcologne.de.. .

Chris Foote wrote:

Hi all.

I have the need to store a large (10M) number of keys in a hash table,
based on a tuple of (long_integer, integer). The standard python
dictionary works well for small numbers of keys, but starts to
perform badly for me inserting roughly 5M keys:

# keys dictionary metakit (both using psyco)
------ ---------- -------
1M 8.8s 22.2s
2M 24.0s 43.7s
5M 115.3s 105.4s

Has anyone written a fast hash module which is more optimal for
large datasets ?

p.s. Disk-based DBs are out of the question because most
key lookups will result in a miss, and lookup time is
critical for this application.

Cheers,
Chris

Python Bindings (\Python24\Lib\ bsddb vers. 4.3.0) and the DLL for
BerkeleyDB (\Python24\DLLs \_bsddb.pyd vers. 4.2.52) are included in the
standard Python 2.4 distribution.

"Berkeley DB was 20 times faster than other databases. It has the
operational speed of a main memory database, the startup and shut down
speed of a disk-resident database, and does not have the overhead of
a client-server inter-process communication."
Ray Van Tassle, Senior Staff Engineer, Motorola

Please let me/us know if it is what you are looking for.

Claudio

sqlite also supports an in-memory database - use pysqlite
(http://initd.org/tracker/pysqlite/wiki) to access this from Python.

-- Paul

[Diez B. Roggisch]

Maric Michaud schrieb:

Le Lundi 15 Mai 2006 19:24, Roy Smith a écrit :

d = {}
d.reserve (10*1000*1000)

d={}.fromkeys(x range(5*10**6)) ?

That is a totally different beast. You don't want to insert arbitrary
keys, you want the internal hash-array to be of the right size.

Diez

[bearophileHUGS]

Roy Smith:

I am befuddled as to why
people thought creating a dict by keyword would be a useful thing to
do, but left out (and, indeed, eliminated the chance to add the syntax
later) the obviously useful ability to hint at the size.

Adding the keyword syntax doesn't require much memory to a Python
programmer because it's the same syntax used elsewhere. While adding
another different method to dicts increases their API. Python is
usually designed to have smaller APIs, to help programmers remember
most things.

I agree that a reserve method to Python dicts/sets can be a little
useful, but Python programmers are usually more concerned about doing
things in a short programmer time and short code space, than telling
the computer how to do such things in the faster way (C++ is more for
speed so the reserve of the STL hashes can be more useful).

Bye,
bearophile