Path: utzoo!utgpu!news-server.csri.toronto.edu!helios.physics.utoronto.ca!ists!yunexus!oz
From: oz@yunexus.yorku.ca (Ozan Yigit)
Newsgroups: comp.lang.perl
Subject: Re: Pattern matching of a large dbm file (slow indexing)
Keywords: pattern matching, assoicative array, dbm
Message-ID: <22673@yunexus.YorkU.CA>
Date: 7 May 91 16:55:58 GMT
References: <1991May6.163310.21805@ccu.umanitoba.ca> <1991May6.223013.7274@iwarp.intel.com>
Sender: news@yunexus.YorkU.CA
Organization: York U. Communications Research & Development
Lines: 42

Brandon S. Allbery writes:

> Standard dbm is slow.

The dbm/ndbm package (as with any other external hashing scheme) is
designed for a particular type of data access, and the result is a single
[on the average] access to database for locating a key and its associated
data.  There may actually be a a slower re-implementation of dbm/ndbm out
there, but in general, the dbm/ndbm and their re-implementations exist
exactly because they work extremely well for the type of access they were
designed for.

So, I can only assume that when you say standard dbm is slow, you really
mean a sequential pass over a database, which dbm is *not* designed for,
is slow.

In tested this assertion for the average use and I found that the usual
sequential scan of keys in the entire dict/words-generated database with
firstkey/nextkey/strncmp (using sdbm) is about 4 times slower than a
fread/strncmp loop over the entire flat version of the database.  I have
not tested the regular ndbm. [2]

On the other hand, BSD HASH [1] with ndbm compatibility routines ran as
fast as the fread/strncmp loop.

I have no idea why perl would be "so slow" in its sequential access
to the database.

oz
---
[1] Seltzer, Margo and Ozan Yigit, ``A New Hash Package for UNIX''
    Proceedings of the USENIX Technical Conference, Dallas, Texas.
    January 1991

[2] sdbm reads the entire database block-by-block during a sequential scan,
but cannot avoid holes, ndbm uses a very clever hash value reconstruction
algorithm to access only the occupied blocks, but is not noticably faster.

---
SunOS: There are many edible ways to serve | internet: oz@nexus.yorku.ca
up scrambled eggs, but one cannot get them | uucp: utzoo/utai!yunexus!oz
back as over-easy or sunny side up.        | phone: [416] 736 5257x33976