[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

APR hash table memory use [was: r11556 causes enormous fsfs memory use]

From: Julian Foad <julianfoad_at_btopenworld.com>
Date: 2004-11-02 22:53:27 CET

Peter N. Lundblad wrote:
> Let's see if we a) mean the same by insert, remove, ... and b) read the
> code the same way:-)
> 1. hash_set(..., non-NULL): entry not found, allocate.
> 2. hash_set(..., NULL) (remove): entry found, remove from linked list
> 3. hash_set(..., non-NULL): entry not found, allocate
> ...
> If you do this, the hash pool will grow for each set. (The above is for
> the same key). We can discuss whose leak it was, but it isn't anymore,
> since I eliminated that usage.

Thanks for clarifying. I understand now:

Every time apr_hash_set(..., non-NULL) adds a new entry, it allocates some pool
memory for that entry and links it into one of its linked lists. When
apr_hash_set(..., NULL) deletes an entry, it unlinks it but does not give that
memory back to the pool.

So this is an inefficiency in APR's implementation of hash tables. It is not
exactly a "leak", since it is contained with a pool, but it is unbounded memory
use caused by repeated simple actions - not a good property for a container to

It would be possible to fix this in APR if people thought it worthwhile, e.g.
by using a "free" list. (Maintain, in the hash table, a list of free entries,
initially empty. When deleting an entry, move it to the "free" list. When a
new entry is wanted, take one from the "free" list if available, else allocate
it from the pool.) This would make the memory used by a hash table
proportional to the maximum number of entries that it had ever held
simultaneously, rather than the number of insertions that had ever been performed.

It seems to me that the APR developers ought to be interested in doing this.
Will I make the effort to take this to their mailing list? Don't know.

- Julian

To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Tue Nov 2 22:53:46 2004

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.