|
From: | Stefan Monnier |
Subject: | Re: Size and length limits for Emacs primitive types and etc data? |
Date: | Wed, 06 Feb 2013 13:46:01 -0500 |
User-agent: | Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux) |
> shown that there are exist implementations with N^2 memory requirement... I don't see any obvious N^2 memory use in that page. All normal implementations I know have a memory use of O(N). Anything different is probably limited to very special application areas (perfect hashing, maybe?). The way hash tables work in the current Emacs implementation is with a table of size N containing (upto) N objects (and N pointers used to reference the next element in a chain), plus a bucket table of size (N / rehash-threshold). Stefan
[Prev in Thread] | Current Thread | [Next in Thread] |