431735 - Use rb.h instead of tree.h

Status: RESOLVED FIXED

(Core :: Memory Allocator, enhancement)

Description

[Jason Evans]

The red-black tree implementation in mozilla/memory/jemalloc/tree.h uses node linkage that includes four fields: parent, left child, right child, and color.  This causes considerable data structure bloat in jemalloc, especially for the unallocated page run trees, since every run must be accessible via two trees.

It is possible to do away with parent pointers and embed the color in the unused least significant bit of one of the child pointers.  For jemalloc this reduces arena chunk headers from 3-->2 and 5-->3 pages for 32- and 64-bit systems, respectively.  It also reduces run header overhead, which allows single-page runs for a larger range of size classes, thus reducing page-level fragmentation.

Comment 1

[Jason Evans]

Attachment: Use rb.h instead of tree.h

Use rb.h instead of tree.h for red-black trees, in order to reduce memory
overhead.

Comment 2

[Jason Evans]

Attachment: Use rb.h instead of tree.h (v2)

Port iterators to Windows, and depend on bug #422960.

Comment 3

[Jason Evans]

Attachment: Use rb.h instead of tree.h (v3)

Add missing typedef for Windows.

Comment 4

[Jason Evans]

Attachment: Use rb.h instead of tree.h (v4)

Add #endif that was accidentally dropped during a merge.

Comment 5

[Jason Evans]

Attachment: Fix Linux build

This patch removes some gcc compiler flags that apparently are not supported in older compilers.  I have tested on Ubuntu 8.04 (gcc 4.2.3) and it appears that these flags are no longer necessary anyway.

Comment 6

[Jason Evans]

changeset:   15460:2f7b7ff816e3
user:        Jason Evans <[e-mail]>
date:        Fri Jun 20 10:34:42 2008 -0700
summary:     Bug 431735: Use rb.h instead of tree.h, r=benjamin

changeset:   15463:dcca5d90ed43
user:        Jason Evans <[e-mail]>
date:        Fri Jun 20 12:00:29 2008 -0700
summary:     Bug 431735: Fix build failures due to compiler flag incompatibilities, r=ted