This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Title: dbmmodule inquiry function is performance prohibitive
Type: performance Stage:
Components: Extension Modules Versions: Python 3.5
Status: open Resolution:
Dependencies: Superseder:
Assigned To: jcea Nosy List: eolson, jafo, jcea, johansen, ysj.ray
Priority: normal Keywords: patch

Created on 2008-02-22 00:41 by johansen, last changed 2022-04-11 14:56 by admin.

File name Uploaded Description Edit
dbm_bool.patch eolson, 2014-04-15 16:33 Add nb_bool for ndbm and gdbm review
dbm_bool_b.patch eolson, 2014-04-15 18:54 Add nb_bool for ndbm and gdbm review
dbm_bool_c.patch eolson, 2014-04-15 20:34 review
dbm_bool_d.patch eolson, 2014-04-16 17:50 Add nb_bool for ndbm and gdbm review
dbm_bool_e.patch eolson, 2014-05-04 15:01 Add nb_bool for ndbm and gdbm review
Messages (23)
msg62668 - (view) Author: johansen (johansen) Date: 2008-02-22 00:41
We've been using Python 2.4 to build the new package management software
for OpenSolaris.  We use a ndbm database to hold keywords about
packages, and found that each time we added a new OpenSolaris build to
our package repository, the time to import would increase by about 1/3
of the previous time.

It turns out that we were continually invoking a function in the
dbmmodule that walked the entire database every time the function was

Looking at dbmmodule.c, the source for, is instructive:

This is dbm_length, the function that we're _always_ calling.

static int
dbm_length(dbmobject *dp)
        if (dp->di_dbm == NULL) {
                 PyErr_SetString(DbmError, "DBM object has already been
                 return -1; 
        if ( dp->di_size < 0 ) {
                datum key;
                int size;

                size = 0;
                for ( key=dbm_firstkey(dp->di_dbm); key.dptr;
                      key = dbm_nextkey(dp->di_dbm))
                dp->di_size = size;
        return dp->di_size;

It's a knock-off of function shown in ndbm(3C) that traverses the
database.  It looks like this function walks every record in the
database, and then returns that as its size.

Further examination of dbmmodule shows that dbm_length has been assigned
as the function for the inquiry operator:

static PyMappingMethods dbm_as_mapping = {
        (inquiry)dbm_length,            /*mp_length*/
        (binaryfunc)dbm_subscript,      /*mp_subscript*/
        (objobjargproc)dbm_ass_sub,     /*mp_ass_subscript*/

It looks like dbm_length stashes the size of the database, so it doesn't
always have to traverse it.  However, further examination of the source
shows that an insertion doesn't update the di_size counter.  Worse yet,
an update or a delete will cause the counter to be set to -1.  This
means that the next call to dbm_length will have to walk the entire
database all over again.  Ick.

One of the problem parts of the code is this line in

                if fmri_list:
                        if not self.searchdb:
                                self.searchdb = \
                          , "c")

This if not triggers the PyObject_IsTrue that invokes the inquiry operator
for the dbm module.  Every time we run this code, we're going to walk
the entire database.  By changing this to:

                if fmri_list:
                        if self.searchdb is None:
                                self.searchdb = \
                          , "c")

We were able to work around the problem by using the is None check,
instead of if not self.searchdb; however, this seems like it is really a
problem with the dbmmodule and should ultimately be resolved there.
msg64126 - (view) Author: Sean Reifschneider (jafo) * (Python committer) Date: 2008-03-19 23:56
Proposed patch is inline.
msg64447 - (view) Author: Jesús Cea Avión (jcea) * (Python committer) Date: 2008-03-24 22:46
I think that "-1" is a sanity check. If the count is updated in the
database, but it is not transactional (or there are bugs, or the DB is
updated by a not up-to-date library, and so on), the cached counter and
the real data can diverge.

Anybody using "Berkeley DB" related databases knows that "length" is
costly. By good reasons, actually :-).

Checking for empty databases should be fast, nevertheless (just iterate
over the first item in the database). We could simply define a
"__nonzero__()" method for that. That would solve the "if" issue.
msg65080 - (view) Author: Jesús Cea Avión (jcea) * (Python committer) Date: 2008-04-07 17:48
Somebody posted a similar issue in pybsddb. The patch I proposed would
be consistent with current "__len__" *internal* use, but the real
intention, I think, is to return True or False if the database is open
or closed, not if the database is empty or not.


msg65081 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2008-04-07 17:51
Assigning anything not related to Py3k design to me is a mistake; I
don't have the bandwidth to handle this, sorry.
msg68106 - (view) Author: Jesús Cea Avión (jcea) * (Python committer) Date: 2008-06-12 23:23
johansen, could you be happy returning True of False according to
database being open/closed?.
msg68107 - (view) Author: johansen (johansen) Date: 2008-06-12 23:29
Yes, True/False should be sufficient for our purposes.  IIRC, we were
trying to determine if we had a stale handle to the database and needed
to open it again.
msg80737 - (view) Author: johansen (johansen) Date: 2009-01-29 01:24
I haven't been able to find any of the patches listed in the comments,
but it does look like providing a nb_nonzero method in the module would
solve our issue.  PyObject_IsTrue checks the tp_as_number methods before
the sequence and mapping methods.  I'm not sure if it's safe to count on
this behavior as always being true, but for 2.4 and the dbmmodule, it
would work.
msg216330 - (view) Author: Eric Olson (eolson) * Date: 2014-04-15 16:33
The performance is still an issue in python 3.
Attaching a patch for python 3, performance numbers are below.

Measuring ndbm time for a falsey check on an open db with 100 entries.  gdbm performance is similar.
Before patch:
    db is not None: 6.9141387939453125e-06
    not db: 0.0006985664367675781
    Factor: 101X (slow)
  After patch:
    db is not None: 4.76837158203125e-06  
    not db: 4.0531158447265625e-06  
    Factor: 1X  (expected)

Also, added a couple tests to verify bool(db) returns the correct value.
msg216361 - (view) Author: Eric Olson (eolson) * Date: 2014-04-15 18:54
Uploading patch with minor test changes (dbm_bool_b.patch).

Backwards compatibility note:

Result of running bool(db) on a db that has been closed:
  Old: _dbm.error: DBM object has already been closed
  With patch: returns False instead of raising.

I think this is desireable, but we could have bool(db) raise an exception when the db is closed if that is preferred for backwards compatibility.
msg216382 - (view) Author: Eric Olson (eolson) * Date: 2014-04-15 20:34
Make the changes backward compatible after getting input on possible problems from r.david.murray
  patch: dbm_bool_c.patch

Now, the only change should be faster performance for bool(db).
msg216519 - (view) Author: Eric Olson (eolson) * Date: 2014-04-16 17:50
New patch with Pep 7 fix - no c++ // style comments. -Thanks johansen.
msg217098 - (view) Author: Jesús Cea Avión (jcea) * (Python committer) Date: 2014-04-23 22:38
First, Python 2.4 has been out of support for a really long time. Deleting.

Eric, let me clarify the situation, because this report is old and I forgot the details.

I think current situation is this, when doing something like "if db : DO_SOMETHING":

a) If the database is closed, raise an exception.

b) If database is empty, returns False.

c) If database has any entry, returns True. Takes time proportional to database length, because it is going to go thru it.

The patch you are proposing:

a) If the database is closed, raise an exception.

b) If database is empty, returns 0.

c) If database has any entry, returns 1. Fast and simply checking if the database has at least a single record.

Why 0/1 instead of True/False?. This is going to be a 3.5 patch, True/False are really there, they are not aliases.

PS: When done, I will probably port this patch to current "pybsddb" work, although I am not sure that Berkeley DB has "firstkey" for all database types it support. Would you allow this porting, Eric?
msg217542 - (view) Author: Jesús Cea Avión (jcea) * (Python committer) Date: 2014-04-29 19:38
Eric, would you mind to clarify the points I raised in the last message?. Lets move this forward.
msg217557 - (view) Author: Eric Olson (eolson) * Date: 2014-04-29 21:30
Thank you for the feedback.  Sorry I didn't see your previous response until today.  I will take a look and respond tonight.
msg217568 - (view) Author: Eric Olson (eolson) * Date: 2014-04-30 04:02
Hi Jesús,

I believe the patch should have this behavior:
  a) If the database is closed, raise an exception.
  b) If database is empty, return False.
  c) If database has any entry, return True. Fast and simply checking if the database has at least a single record.

The 0/1 appears to be converted to Py_TRUE/Py_FALSE in PyObject_IsTrue() in boolobject.c.

For background, here's the code path I'm seeing:

bool_new(...)                        (in Objects/boolobject.c)
  ok = PyObject_IsTrue(obj)          (in Objects/object.c)
  return PyBool_FromLong(ok)

Looking at PyObject_IsTrue is informative.  It shows that since tp_as_number->nb_bool is defined (as dbm_bool), it is used instead of the old default of tp_as_mapping->mp_length.

I'm still learning CPython, and I'm not sure if everything goes through bool_new(), but I think this makes sense.  If you see more places I can/should look for details here, let me know.
msg217662 - (view) Author: Eric Olson (eolson) * Date: 2014-04-30 22:25
Also, I'm happy to allow the code to be ported to pybsddb. As long as it doesn't cause any problems with CPython licensing - and I can't think of any way it could.
msg217669 - (view) Author: Jesús Cea Avión (jcea) * (Python committer) Date: 2014-05-01 00:27
I would like a bit more comfortable if you return True/False. Maybe I am missing something, I am not familiar with this either, but looks like more... sensible, instead of counting on implicit and magical 0/1 -> False/True conversion.

What do you think?. Maybe I am missing something, I am not familiar with the details either.
msg217670 - (view) Author: Jesús Cea Avión (jcea) * (Python committer) Date: 2014-05-01 00:29
BTW, would you mind to sign a contributor form?.
msg217671 - (view) Author: Jesús Cea Avión (jcea) * (Python committer) Date: 2014-05-01 00:30
Oh, I see that your already did. Sorry for the noise.
msg217676 - (view) Author: Eric Olson (eolson) * Date: 2014-05-01 03:08
I did try the suggestion to return Py_False, but that gives the wrong result since Py_False is not 0 and gets returned as Py_True.

I looked for similar code, and this looks like the convention for handling "if obj".  PyObject_IsTrue() is called on the object.  What it returns can be affected by an nb_bool function that returns 0 or 1 (or -1).

Here are a few similar examples that need to implement nb_bool to handle converting an obj to a bool:

For many types, there is no nb_bool, and other things are tried such as getting the length.
msg217685 - (view) Author: Jesús Cea Avión (jcea) * (Python committer) Date: 2014-05-01 10:49
OK, you did your homework.

I checked "PyObject_Is_True()" function and I agree. This actually looks like a "leak" when True/False were added to Python. Python3 is inheriting it :-).


I see three issues in the code:

a) You are getting a key from the database, and you are not freeing it. So, this code leaks memory.

b) You should check database errors too. Documentation says "When the end of the database is reached, the dptr member of the key is a null pointer. If an error is detected, the dptr member of the key shall be a null pointer and the error condition of the database shall be set.". Raise an exception with the proper error. Would be nice to test that too, but it is probably nos possible.

c) Please, use NULL instead of "0".

Thanks for your effort, Eric.
msg217877 - (view) Author: Eric Olson (eolson) * Date: 2014-05-04 15:01
Thanks for finding those issues.  I attached a new patch.

a) Good find, I added the free() for gdbm.  ndbm doesn't need free().
b) Added the error check.  I don't know if a test can be made for this.  If there was a common way to patch C libraries in CPython, I would give that a try.
Also, do you know if we should check for the gdbm error before the dbm error, or does it not matter?
c) Yes, it looks like NULL is used here instead of 0.  Changed 0s to NULLS.

Let me know if you see anything else.
Date User Action Args
2022-04-11 14:56:31adminsetgithub: 46412
2014-05-04 15:01:48eolsonsetfiles: + dbm_bool_e.patch

messages: + msg217877
2014-05-01 10:49:06jceasetassignee: jcea
messages: + msg217685
2014-05-01 03:08:00eolsonsetmessages: + msg217676
2014-05-01 00:30:53jceasetmessages: + msg217671
2014-05-01 00:29:47jceasetmessages: + msg217670
2014-05-01 00:27:24jceasetmessages: + msg217669
2014-04-30 22:25:39eolsonsetmessages: + msg217662
2014-04-30 04:02:11eolsonsetmessages: + msg217568
2014-04-29 21:30:41eolsonsetmessages: + msg217557
2014-04-29 19:38:14jceasetmessages: + msg217542
2014-04-23 22:38:31jceasetmessages: + msg217098
versions: - Python 2.4
2014-04-16 17:50:48eolsonsetfiles: + dbm_bool_d.patch

messages: + msg216519
2014-04-15 20:34:27eolsonsetfiles: + dbm_bool_c.patch

messages: + msg216382
versions: + Python 3.5
2014-04-15 18:54:17eolsonsetfiles: + dbm_bool_b.patch

messages: + msg216361
2014-04-15 16:33:15eolsonsetfiles: + dbm_bool.patch
nosy: + eolson
messages: + msg216330

2011-02-22 13:53:04ysj.raysetnosy: + ysj.ray
2009-01-29 02:02:27gvanrossumsetnosy: - gvanrossum
2009-01-29 01:24:14johansensetmessages: + msg80737
2008-06-12 23:29:59johansensetmessages: + msg68107
2008-06-12 23:23:33jceasetmessages: + msg68106
2008-04-07 17:51:05gvanrossumsetassignee: gvanrossum -> (no value)
messages: + msg65081
2008-04-07 17:48:03jceasetmessages: + msg65080
2008-03-24 22:46:49jceasetmessages: + msg64447
2008-03-24 22:45:08benjamin.petersonsettype: resource usage -> performance
2008-03-24 22:33:05jceasetnosy: + jcea
2008-03-19 23:56:58jafosetpriority: normal
assignee: gvanrossum
messages: + msg64126
keywords: + patch
nosy: + gvanrossum, jafo
2008-02-22 00:41:15johansencreate