Content preview: Le 29/01/15 08:25, Howard Chu a écrit : > Emmanuel Lécharny
wrote: >> Le 29/01/15 04:20, Howard Chu a écrit : >>> ITS#8038 (syncrepl
hanging onto its presentlist) only came to my >>> attention due to the amount
of memory involved. On a refresh of a DB >>> with 2.8M entries I saw the
consumer using about 320MB just for the >>> presentlist. This list consists
solely of 16 byte entryUUIDs; 2.8M >>> items should have used no more than
48MB. An AVL node itself is 28 >>> bytes on 64-bit platform, plus 16 bytes
for the struct berval wrapped >>> around the UUID. >>> >>> I'm looking into
adding an in-memory B+tree library to liblutil. For >>> the type of fixed-size
records we're usually storing in AVL trees, a >>> Btree will be much more
compact and higher performance since it will >>> need rebalancing far less
frequently. >>> >> Why using a B+tree ? A hash map wouldn't be a more appropriate
data >> structure ? EntryUUID ordering seems overkilling... > > I'm not fond
of hashes, they're always cache-unfriendly and most of > them have very poor
dynamic growth behavior. Since we don't know in > advance how many IDs are
being stored, growth/resizing is a major > concern. Tree structures are generally
preferred because they have > very good incremental growth performance, and
B+trees have the best > CPU cache behavior. Hashes have three problems :
- first, as you say, growing a hash is a matter of copying the hash completely
(most of the time) - second, they can degenerate - third, they have an average
emptiness of roughly 30% [...]
Content analysis details: (-2.0 points, 5.0 required)
pts rule name description
---- ---------------------- --------------------------------------------------
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(elecharny[at]gmail.com)
0.0 RCVD_IN_DNSWL_BLOCKED RBL: ADMINISTRATOR NOTICE: The query to DNSWL
was blocked. See
http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block
for more information.
[209.85.212.179 listed in list.dnswl.org]
-0.0 SPF_PASS SPF: sender matches SPF record
-1.9 BAYES_00 BODY: Bayes spam probability is 0 to 1%
[score: 0.0000]
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's
domain
0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-BeenThere: openldap-***@openldap.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: OpenLDAP development discussion list <openldap-devel.openldap.org>
List-Unsubscribe: <http://www.openldap.org/lists/mm/options/openldap-devel>,
<mailto:openldap-devel-***@openldap.org?subject=unsubscribe>
List-Archive: <http://www.openldap.org/lists/openldap-devel/>
List-Post: <mailto:openldap-***@openldap.org>
List-Help: <mailto:openldap-devel-***@openldap.org?subject=help>
List-Subscribe: <http://www.openldap.org/lists/mm/listinfo/openldap-devel>,
<mailto:openldap-devel-***@openldap.org?subject=subscribe>
Errors-To: openldap-devel-***@openldap.org
Sender: "openldap-devel" <openldap-devel-***@openldap.org>
X-Spam-Score: -2.0 (--)
X-Spam-Report: Spam detection software, running on the system "gauss.openldap.net", has
identified this incoming email as possible spam. The original message
has been attached to this so you can view it (if it isn't spam) or label
similar future email. If you have any questions, see
the administrator of that system for details.
Content preview: Le 29/01/15 08:25, Howard Chu a écrit : > Emmanuel Lécharny
wrote: >> Le 29/01/15 04:20, Howard Chu a écrit : >>> ITS#8038 (syncrepl
hanging onto its presentlist) only came to my >>> attention due to the amount
of memory involved. On a refresh of a DB >>> with 2.8M entries I saw the
consumer using about 320MB just for the >>> presentlist. This list consists
solely of 16 byte entryUUIDs; 2.8M >>> items should have used no more than
48MB. An AVL node itself is 28 >>> bytes on 64-bit platform, plus 16 bytes
for the struct berval wrapped >>> around the UUID. >>> >>> I'm looking into
adding an in-memory B+tree library to liblutil. For >>> the type of fixed-size
records we're usually storing in AVL trees, a >>> Btree will be much more
compact and higher performance since it will >>> need rebalancing far less
frequently. >>> >> Why using a B+tree ? A hash map wouldn't be a more appropriate
data >> structure ? EntryUUID ordering seems overkilling... > > I'm not fond
of hashes, they're always cache-unfriendly and most of > them have very poor
dynamic growth behavior. Since we don't know in > advance how many IDs are
being stored, growth/resizing is a major > concern. Tree structures are generally
preferred because they have > very good incremental growth performance, and
B+trees have the best > CPU cache behavior. Hashes have three problems :
- first, as you say, growing a hash is a matter of copying the hash completely
(most of the time) - second, they can degenerate - third, they have an average
emptiness of roughly 30% [...]
Content analysis details: (-2.0 points, 5.0 required)
pts rule name description
---- ---------------------- --------------------------------------------------
0.0 RCVD_IN_DNSWL_BLOCKED RBL: ADMINISTRATOR NOTICE: The query to DNSWL
was blocked. See
http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block
for more information.
[209.85.212.179 listed in list.dnswl.org]
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(elecharny[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
-1.9 BAYES_00 BODY: Bayes spam probability is 0 to 1%
[score: 0.0000]
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's
domain
0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
Post by Howard ChuPost by Emmanuel LécharnyPost by Howard ChuITS#8038 (syncrepl hanging onto its presentlist) only came to my
attention due to the amount of memory involved. On a refresh of a DB
with 2.8M entries I saw the consumer using about 320MB just for the
presentlist. This list consists solely of 16 byte entryUUIDs; 2.8M
items should have used no more than 48MB. An AVL node itself is 28
bytes on 64-bit platform, plus 16 bytes for the struct berval wrapped
around the UUID.
I'm looking into adding an in-memory B+tree library to liblutil. For
the type of fixed-size records we're usually storing in AVL trees, a
Btree will be much more compact and higher performance since it will
need rebalancing far less frequently.
Why using a B+tree ? A hash map wouldn't be a more appropriate data
structure ? EntryUUID ordering seems overkilling...
I'm not fond of hashes, they're always cache-unfriendly and most of
them have very poor dynamic growth behavior. Since we don't know in
advance how many IDs are being stored, growth/resizing is a major
concern. Tree structures are generally preferred because they have
very good incremental growth performance, and B+trees have the best
CPU cache behavior.
Hashes have three problems :
- first, as you say, growing a hash is a matter of copying the hash
completely (most of the time)
- second, they can degenerate
- third, they have an average emptiness of roughly 30%
Now, on average, with data that are well distributed, they have some
major advantages :
- they are faster than any other data structure, with a O(1) average
lookup cost
- the memory that it uses is minimal, as it's generally backed with an
array containing the data plus a flag that indicates a follow link if
the bucket is shared by more than one element
- adding and deleting elements in a hash map is generally not expensive
If you compare it with a B+tree, which is stable in O(logN), it's
faster, uses less memory, and it's easier to implement. The most
criticial point being that addition or removal from a hash is way less
expensive than for e BTree. You can also protect the hash against
concurrent access way more than a B+Tree, by splitting the buckets in
blocks of sub-buckets, with a lock being set on each separated block.
At this point, some real world experiment is needed to validate those
approaches.