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

[Klaas]

>22.2s 20m25s[3]

20m to insert 1m keys? You are doing something wrong.

With bdb's it is crucial to insert keys in bytestring-sorted order.
Also, be sure to give it a decent amount of cache.

-Mike

[Chris Foote]

Klaas wrote:

22.2s 20m25s[3]
20m to insert 1m keys? You are doing something wrong.

Hi Mike.

I've put together some simplified test code, but the bsddb
module gives 11m for 1M keys:

Number generator test for 1000000 number ranges
with a maximum of 3 wildcard digits.
Wed May 17 22:18:17 2006 dictionary population started
Wed May 17 22:18:26 2006 dictionary population stopped, duration 8.6s
Wed May 17 22:18:27 2006 StorageBerkeley DB population started
Wed May 17 22:29:32 2006 StorageBerkeley DB population stopped, duration 665.6s
Wed May 17 22:29:33 2006 StorageSQLite population started
Wed May 17 22:30:38 2006 StorageSQLite population stopped, duration 65.5s

test code is attached.
With bdb's it is crucial to insert keys in bytestring-sorted order.
For the bsddb test, I'm using a plain string. (The module docs list a
string being the only datatype supported for both keys & values).
Also, be sure to give it a decent amount of cache.

The bsddb.hashopen( ) factory seems to have a bug in this regard; if you
supply a cachesize argument, then it barfs:

....
File "bsddb-test.py", line 67, in runtest
db = bsddb.hashopen( None, flag='c', cachesize=8192)
File "/usr/lib/python2.4/bsddb/__init__.py", line 288, in hashopen
if cachesize is not None: d.set_cachesize (0, cachesize)
bsddb._db.DBInv alidArgError: (22, 'Invalid argument -- DB->set_cachesiz e: method not permitted when environment
specified')
I'll file a bug report on this if it isn't already fixed.

Cheers,
Chris

[Claudio Grondi]

Chris Foote wrote:

Klaas wrote:

22.2s 20m25s[3]

20m to insert 1m keys? You are doing something wrong.

Hi Mike.

I've put together some simplified test code, but the bsddb
module gives 11m for 1M keys:

I have run your code for the bsddb on my P4 2.8 GHz and have got:
Number generator test for 1000000 number ranges
with a maximum of 3 wildcard digits.
Wed May 17 16:34:06 2006 dictionary population started
Wed May 17 16:34:14 2006 dictionary population stopped, duration 8.4s
Wed May 17 16:34:14 2006 StorageBerkeley DB population started
Wed May 17 16:35:59 2006 StorageBerkeley DB population stopped, duration
104.3s
Surprising here, that the dictionary population gives the same time, but
the BerkeleyDB inserts the records 6 times faster on my computer than on
yours. I am running Python 2.4.2 on Windows XP SP2, and you?
Number generator test for 1000000 number ranges
with a maximum of 3 wildcard digits.
Wed May 17 22:18:17 2006 dictionary population started
Wed May 17 22:18:26 2006 dictionary population stopped, duration 8.6s
Wed May 17 22:18:27 2006 StorageBerkeley DB population started
Wed May 17 22:29:32 2006 StorageBerkeley DB population stopped, duration
665.6s
Wed May 17 22:29:33 2006 StorageSQLite population started
Wed May 17 22:30:38 2006 StorageSQLite population stopped, duration 65.5s As I don't have SQLite installed, it is interesting to see if the factor
10 in the speed difference between BerkeleyDB and SQLite can be
confirmed by someone else.
Why is SQLite faster here? I suppose, that SQLite first adds all the
records and builds the index afterwards with all the records there (with
db.commit()).
Can the same be done in BerkeleyDB, or does BerkeleyDB not support
inserting of records without building an index each single insert
command? If yes, how?

Claudio
test code is attached.

With bdb's it is crucial to insert keys in bytestring-sorted order.

For the bsddb test, I'm using a plain string. (The module docs list a
string being the only datatype supported for both keys & values).

Also, be sure to give it a decent amount of cache.

The bsddb.hashopen( ) factory seems to have a bug in this regard; if you
supply a cachesize argument, then it barfs:

....
File "bsddb-test.py", line 67, in runtest
db = bsddb.hashopen( None, flag='c', cachesize=8192)
File "/usr/lib/python2.4/bsddb/__init__.py", line 288, in hashopen
if cachesize is not None: d.set_cachesize (0, cachesize)
bsddb._db.DBInv alidArgError: (22, 'Invalid argument --
DB->set_cachesiz e: method not permitted when environment specified')
I'll file a bug report on this if it isn't already fixed.

Cheers,
Chris
------------------------------------------------------------------------

import bsddb
import random
import time
import sqlite

import psyco
psyco.full()

class WallClockTimer( object):
'''Simple timer for measuring tests.'''
def __init__(self, msg):
self.start = time.time()
self.msg = msg
print time.ctime(self .start), self.msg, 'started'

def stop(self):
end = time.time()
duration = end - self.start
print time.ctime(end) , self.msg, 'stopped, duration %.1fs' % duration

class NumberGen(objec t):
'''Phone number generator for testing different methods of storage.'''
def __init__(self, range_start, range_end, n, max_wildcards):

print '''Number generator test for %d number ranges
with a maximum of %d wildcard digits.''' % (n, max_wildcards)

wildcards = range(0, max_wildcards + 1)
# generate n unique numbers and store as keys in number_hash
timer = WallClockTimer( 'dictionary population')
self.number_has h = {}

for i in xrange(0, n):
unique = False
while not unique:
wildcard_digits = self.gen_wildca rd_digits(wildc ards)
num = self.gen_number (range_start, range_end)
if wildcard_digits > 0:
num /= (10 ** wildcard_digits )
key = (num, wildcard_digits )
if self.number_has h.has_key(key):
unique = False
else:
unique = True
self.number_has h[key] = None
timer.stop()

def gen_wildcard_di gits(self, wildcards):
return random.choice(w ildcards)

def gen_number(self , start, end):
return int(random.unif orm(start, end))

def storage_test(se lf, StorageTestClas s):
test = StorageTestClas s(self.number_h ash)

class StorageTest(obj ect):
'''base class for testing storage. Derive a test
class and provide your own runtest() method.'''
def __init__(self, number_hash):
timer = WallClockTimer( '%s population' % type(self).__na me__)
self.runtest(nu mber_hash)
timer.stop()

class StorageBerkeley DB(StorageTest) :
def runtest(self, number_hash):
db = bsddb.hashopen( None, flag='c', cachesize=8192)
for (num, wildcard_digits ) in number_hash.key s():
key = '%d:%d' % (num, wildcard_digits )
db[key] = None
db.close()

class StorageSQLite(S torageTest):
def runtest(self, number_hash):
db = sqlite.connect( ':memory:')
cursor = db.cursor()
cursor.execute( 'CREATE TABLE numbers (num INTEGER, wd INTEGER)')
q = """insert into numbers (num, wd) values (%d, %d)"""
for (num, wildcard_digits ) in number_hash.key s():
cursor.execute( q, num, wildcard_digits )
db.commit()
db.close()
if __name__ == '__main__':

test_vals = {'range_start' : 61880 * 10 ** 7,
'range_end' : 61891 * 10 ** 7,
'n' : 1 * 10 ** 4,
'max_wildcards' : 3}

ngen = NumberGen(test_ vals['range_start'], test_vals['range_end'],
test_vals['n'], test_vals['max_wildcards'])

ngen.storage_te st(StorageBerke leyDB)
ngen.storage_te st(StorageSQLit e)

[Chris Foote]

Richie Hindle wrote:

[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."

Thanks for the suggestion Richie. PyJudy works brilliantly :-)

Cheers,
Chris

[Chris Foote]

Claudio Grondi wrote:

Chris Foote wrote:

Klaas wrote:

22.2s 20m25s[3]

20m to insert 1m keys? You are doing something wrong.

I've put together some simplified test code, but the bsddb
module gives 11m for 1M keys:

I have run your code for the bsddb on my P4 2.8 GHz and have got:
Number generator test for 1000000 number ranges
with a maximum of 3 wildcard digits.
Wed May 17 16:34:06 2006 dictionary population started
Wed May 17 16:34:14 2006 dictionary population stopped, duration 8.4s
Wed May 17 16:34:14 2006 StorageBerkeley DB population started
Wed May 17 16:35:59 2006 StorageBerkeley DB population stopped, duration
104.3s

Surprising here, that the dictionary population gives the same time, but
the BerkeleyDB inserts the records 6 times faster on my computer than on
yours. I am running Python 2.4.2 on Windows XP SP2, and you?

Fedora core 5 with ext3 filesystem. The difference will be due to
the way that Windows buffers writes for the filesystem you're using
(it sounds like you're using a FAT-based file system).

Number generator test for 1000000 number ranges
with a maximum of 3 wildcard digits.
Wed May 17 22:18:17 2006 dictionary population started
Wed May 17 22:18:26 2006 dictionary population stopped, duration 8.6s
Wed May 17 22:18:27 2006 StorageBerkeley DB population started
Wed May 17 22:29:32 2006 StorageBerkeley DB population stopped,
duration 665.6s
Wed May 17 22:29:33 2006 StorageSQLite population started
Wed May 17 22:30:38 2006 StorageSQLite population stopped, duration 65.5s

As I don't have SQLite installed, it is interesting to see if the factor
10 in the speed difference between BerkeleyDB and SQLite can be
confirmed by someone else.
Why is SQLite faster here? I suppose, that SQLite first adds all the
records and builds the index afterwards with all the records there (with
db.commit()).

SQLite is way faster because BerkeleyDB always uses a disk file,
and SQLite is in RAM only.

Cheers,
Chris

[Claudio Grondi]

Chris Foote wrote:

Claudio Grondi wrote:

Chris Foote wrote:

Klaas wrote:

> 22.2s 20m25s[3]

20m to insert 1m keys? You are doing something wrong.

I've put together some simplified test code, but the bsddb
module gives 11m for 1M keys:
I have run your code for the bsddb on my P4 2.8 GHz and have got:
Number generator test for 1000000 number ranges
with a maximum of 3 wildcard digits.
Wed May 17 16:34:06 2006 dictionary population started
Wed May 17 16:34:14 2006 dictionary population stopped, duration 8.4s
Wed May 17 16:34:14 2006 StorageBerkeley DB population started
Wed May 17 16:35:59 2006 StorageBerkeley DB population stopped,
duration 104.3s
>
Surprising here, that the dictionary population gives the same time,
but the BerkeleyDB inserts the records 6 times faster on my computer
than on yours. I am running Python 2.4.2 on Windows XP SP2, and you?

Fedora core 5 with ext3 filesystem. The difference will be due to
the way that Windows buffers writes for the filesystem you're using
(it sounds like you're using a FAT-based file system).

Ok, according to the Windows task manager the Python process
reads/writes to the file system during the run of BerkeleyDB test around
7 GByte(!) of data and the hard drive is continuously busy, where the
size of file I found in the Temp directory is always below 20 MByte. The
hard drive access is probably the main reason for loosing time - here a
question to BerkeleyDB experts:

Can the BerkeleyDB via Python bsddb3 interface be tuned to use only RAM
or as BerkeleyDB can scale to larger data amount it makes not much sense
to tweak it into RAM?

Chris, is maybe a RAM-disk the right way to go here to save time lost
for accessing the file stored in the file system on the hard drive?

The RAM requirements, according to Windows XP task manager, are below
100 MByte. I am using the NTFS file system (yes, I know, that FAT is in
some configurations faster than NTFS) and XP Professional SP2 without
any tuning of file system caching. The CPU is 100% busy.

What CPU and RAM (SIMM, DDR, DDR2) do you have? I have 2GByte fast DDR
PC400/3200 dual line RAM. It seems, that you are still not getting
results within the range others experience running your code, so I
suppose, it has something to do with the hardware you are using.

Number generator test for 1000000 number ranges
with a maximum of 3 wildcard digits.
Wed May 17 22:18:17 2006 dictionary population started
Wed May 17 22:18:26 2006 dictionary population stopped, duration 8.6s
Wed May 17 22:18:27 2006 StorageBerkeley DB population started
Wed May 17 22:29:32 2006 StorageBerkeley DB population stopped,
duration 665.6s
Wed May 17 22:29:33 2006 StorageSQLite population started
Wed May 17 22:30:38 2006 StorageSQLite population stopped, duration
65.5s As I don't have SQLite installed, it is interesting to see if the
factor 10 in the speed difference between BerkeleyDB and SQLite can be
confirmed by someone else.
Why is SQLite faster here? I suppose, that SQLite first adds all the
records and builds the index afterwards with all the records there
(with db.commit()).

SQLite is way faster because BerkeleyDB always uses a disk file,
and SQLite is in RAM only.

One of the reasons I put an eye on BerkeleyDB is that it pretends to
scale to a huge amount (Terrabyte) of data and don't need as much RAM as
Python dictionary and it is not necessary to save/load pickled version
of the data (i.e. here the dictionary) from/to RAM in order to work with
it.
I guess, that in your case BerkeleyDB is for the named reasons probably
the right way to go, except your data will stay small and the Python
dictionary with them will always fit into RAM.

Now I am curious to know which path you have decided to go and why?

Claudio
Cheers,
Chris

[Claudio Grondi]

Chris Foote wrote:

Richie Hindle wrote:

[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."

Thanks for the suggestion Richie. PyJudy works brilliantly :-)

Cheers,
Chris

It seems, that there is no Microsoft Windows version of Judy available,
so for this reason PyJudy won't work on Windows - am I right?

Claudio

[Klaas]

Chris:

Berkeley DB is great for accessing data by key for things already
stored on disk (i.e. read access), but write performance for each
key-value pair is slow due to it being careful about flushing
writes to disk by default.

This is absolutely false.

-Mike

[Klaas]

Chris:

class StorageBerkeley DB(StorageTest) :
def runtest(self, number_hash):
db = bsddb.hashopen( None, flag='c', cachesize=8192)
for (num, wildcard_digits ) in number_hash.key s():
key = '%d:%d' % (num, wildcard_digits )
db[key] = None
db.close()

BDBs can accomplish what you're looking to do, but they need to be
tuned carefully. I won't get into too many details here, but you have
a few fatal flaws in that code.

1. 8Kb of cache is _pathetic_. Give it a few hundred megs. This is by
far your nbiggest problem.
2. Use BTREE unless you have a good reason to use DBHASH
3. Use proper bdb env creation instead of the hash_open apis.
4. Insert your keys in sorted order.

-Mike

[Thomas Ganss]

Klaas schrieb:

4. Insert your keys in sorted order.

This advice is questionable -
it depends on the at least on the db vendor and probably
sometimes on the sort method, if inserting pre-sorted
values is better.

My gut feeling on this matter is:
IF the insert times of pre-sorted values is far better
than the times of unsorted values, there is a chance
that the resulting tree is unbalanced: only 1 compare
operation after insert and no re-balancing of the tree.

re-indexing will probably give you far better access times
in this case. Another option is to drop non RI indexes used only
for query optimization and recreate them after batch insert.

my 0.02 EUR

thomas