[cairo-commit] 3 commits - src/cairo-skiplist.c
src/cairo-skiplist-private.h
Behdad Esfahbod
behdad at kemper.freedesktop.org
Mon Apr 9 16:39:49 PDT 2007
src/cairo-skiplist-private.h | 15 +++++++++++++--
src/cairo-skiplist.c | 28 +++++++++++++++++++---------
2 files changed, 32 insertions(+), 11 deletions(-)
New commits:
diff-tree b6924722b8c8e5f4356d3c8ba438a702ffb8a5ed (from 6daaf8a89d24fb3022687fe8d52c8001dc270265)
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Sun Apr 8 23:35:01 2007 -0400
[cairo-skiplist] Use one random number per insertion, instead of two
diff --git a/src/cairo-skiplist-private.h b/src/cairo-skiplist-private.h
index cf1a99b..3a948af 100644
--- a/src/cairo-skiplist-private.h
+++ b/src/cairo-skiplist-private.h
@@ -32,6 +32,9 @@
* http://citeseer.ist.psu.edu/pugh90skip.html
*/
+/* Note that random_level() called from alloc_node_for_level() depends on
+ * this being not more than 16.
+ */
#define MAX_LEVEL 15
/* Returns the index of the free-list to use for a node at level 'level' */
diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c
index 52d8465..2d2fbb0 100644
--- a/src/cairo-skiplist.c
+++ b/src/cairo-skiplist.c
@@ -269,9 +269,12 @@ _cairo_skip_list_fini (cairo_skip_list_t
static int
random_level (void)
{
- /* tricky bit -- each bit is '1' 75% of the time */
- long int bits = lfsr_random() | lfsr_random();
int level = 0;
+ /* tricky bit -- each bit is '1' 75% of the time.
+ * This works because we only use the lower MAX_LEVEL
+ * bits, and MAX_LEVEL < 16 */
+ long int bits = lfsr_random();
+ bits |= bits >> 16;
while (++level < MAX_LEVEL)
{
diff-tree 6daaf8a89d24fb3022687fe8d52c8001dc270265 (from a7de9501f6d0f3a574c5246b81d78aa749b64e67)
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Sun Apr 8 23:32:27 2007 -0400
[cairo-skiplist] Reduce MAX_LEVEL from 31 to 15
The probability that a node of level L is generated is
0.25^(L-1) * 0.75. It means, a node of level 15 or
more will be used with a probability of about 3 * 10^-9.
That's really rare...
Actually that's not still true, because the level of a new
node is capped by current max-level plus one. So to really
get a node with a level of 15 one should first get a node
of level 2, then 3, then 4, ..., finally 15. Now that's
REALLY rare.
And guess what, the skiplist only start behaving bad with a
max level cap of MAX_LEVEL when having on the order of
4**MAX_LEVEL items in it. I really hope we don't get there.
diff --git a/src/cairo-skiplist-private.h b/src/cairo-skiplist-private.h
index 4be1aa0..cf1a99b 100644
--- a/src/cairo-skiplist-private.h
+++ b/src/cairo-skiplist-private.h
@@ -32,7 +32,7 @@
* http://citeseer.ist.psu.edu/pugh90skip.html
*/
-#define MAX_LEVEL 31
+#define MAX_LEVEL 15
/* Returns the index of the free-list to use for a node at level 'level' */
#define FREELIST_FOR_LEVEL(level) (((level) - 1) / 2)
diff-tree a7de9501f6d0f3a574c5246b81d78aa749b64e67 (from 9da86e4a386505288c3a933f30583abf7706c950)
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Sun Apr 8 23:24:50 2007 -0400
[cairo-skiplist] Group levels two-by-two in freelists
Most memory allocators allocate in multiples of twice the size of
a pointer. So there is no point in keeping freelists for both
even and odd levels. We now round odd levels up to the next
even level for freelist computations. This reduces the number of
node mallocations.
diff --git a/src/cairo-skiplist-private.h b/src/cairo-skiplist-private.h
index 2ad4034..4be1aa0 100644
--- a/src/cairo-skiplist-private.h
+++ b/src/cairo-skiplist-private.h
@@ -34,6 +34,14 @@
#define MAX_LEVEL 31
+/* Returns the index of the free-list to use for a node at level 'level' */
+#define FREELIST_FOR_LEVEL(level) (((level) - 1) / 2)
+
+/* Returns the maximum level that uses the same free-list as 'level' does */
+#define FREELIST_MAX_LEVEL_FOR(level) (((level) + 1) & ~1)
+
+#define MAX_FREELIST_LEVEL (FREELIST_FOR_LEVEL (MAX_LEVEL - 1) + 1)
+
/*
* Skip list element. In order to use the skip list, the caller must
* generate a structure for list elements that has as its final member
@@ -58,7 +66,7 @@ typedef struct _skip_list {
size_t elt_size;
size_t data_size;
skip_elt_t *chains[MAX_LEVEL];
- skip_elt_t *freelists[MAX_LEVEL];
+ skip_elt_t *freelists[MAX_FREELIST_LEVEL];
int max_level;
} cairo_skip_list_t;
diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c
index c8a3018..52d8465 100644
--- a/src/cairo-skiplist.c
+++ b/src/cairo-skiplist.c
@@ -232,6 +232,9 @@ _cairo_skip_list_init (cairo_skip_list_t
for (i = 0; i < MAX_LEVEL; i++) {
list->chains[i] = NULL;
+ }
+
+ for (i = 0; i < MAX_FREELIST_LEVEL; i++) {
list->freelists[i] = NULL;
}
@@ -247,7 +250,7 @@ _cairo_skip_list_fini (cairo_skip_list_t
while ((elt = list->chains[0])) {
_cairo_skip_list_delete_given (list, elt);
}
- for (i=0; i<MAX_LEVEL; i++) {
+ for (i=0; i<MAX_FREELIST_LEVEL; i++) {
elt = list->freelists[i];
while (elt) {
skip_elt_t *nextfree = elt->prev;
@@ -282,19 +285,23 @@ random_level (void)
static void *
alloc_node_for_level (cairo_skip_list_t *list, unsigned level)
{
- if (list->freelists[level-1]) {
- skip_elt_t *elt = list->freelists[level-1];
- list->freelists[level-1] = elt->prev;
+ int freelist_level = FREELIST_FOR_LEVEL (level);
+ if (list->freelists[freelist_level]) {
+ skip_elt_t *elt = list->freelists[freelist_level];
+ list->freelists[freelist_level] = elt->prev;
return ELT_DATA(elt);
}
- return malloc (list->elt_size + (level-1) * sizeof (skip_elt_t *));
+ return malloc (list->elt_size
+ + (FREELIST_MAX_LEVEL_FOR (level) - 1) * sizeof (skip_elt_t *));
}
static void
free_elt (cairo_skip_list_t *list, skip_elt_t *elt)
{
- elt->prev = list->freelists[elt->prev_index];
- list->freelists[elt->prev_index] = elt;
+ int level = elt->prev_index + 1;
+ int freelist_level = FREELIST_FOR_LEVEL (level);
+ elt->prev = list->freelists[freelist_level];
+ list->freelists[freelist_level] = elt;
}
/*
More information about the cairo-commit
mailing list