[cairo-commit] 2 commits - build/configure.ac.system perf/cairo-perf-posix.c util/cairo-script
Chris Wilson
ickle at kemper.freedesktop.org
Sat Jun 6 05:52:41 PDT 2009
build/configure.ac.system | 9 +-
perf/cairo-perf-posix.c | 72 +++++++++++++++-----
util/cairo-script/cairo-script-hash.c | 109 ++++++++++++++++++++-----------
util/cairo-script/cairo-script-private.h | 1
4 files changed, 133 insertions(+), 58 deletions(-)
New commits:
commit d753ba96aba4dbbcbd0da1823be8824ba233f079
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Fri Jun 5 17:59:38 2009 +0100
[script] Manage used entries within hash tables
Apply the patch from Karl Tomlinson,
https://bugs.freedesktop.org/attachment.cgi?id=19802, to repack the hash
table if the number of free slots falls too low.
diff --git a/util/cairo-script/cairo-script-hash.c b/util/cairo-script/cairo-script-hash.c
index 6745111..c82a297 100644
--- a/util/cairo-script/cairo-script-hash.c
+++ b/util/cairo-script/cairo-script-hash.c
@@ -34,6 +34,7 @@
* Keith Packard <keithp at keithp.com>
* Graydon Hoare <graydon at redhat.com>
* Carl Worth <cworth at cworth.org>
+ * Karl Tomlinson <karlt+ at karlt.net>, Mozilla Corporation
*/
#include "cairo-script-private.h"
@@ -60,16 +61,8 @@
#define ENTRY_IS_DEAD(entry) ((entry) == DEAD_ENTRY)
#define ENTRY_IS_LIVE(entry) ((entry) > DEAD_ENTRY)
-/* We expect keys will not be destroyed frequently, so our table does not
- * contain any explicit shrinking code nor any chain-coalescing code for
- * entries randomly deleted by memory pressure (except during rehashing, of
- * course). These assumptions are potentially bad, but they make the
- * implementation straightforward.
- *
- * Revisit later if evidence appears that we're using excessive memory from
- * a mostly-dead table.
- *
- * This table is open-addressed with double hashing. Each table size is a
+
+/* This table is open-addressed with double hashing. Each table size is a
* prime chosen to be a little more than double the high water mark for a
* given arrangement, so the tables should remain < 50% full. The table
* size makes for the "first" hash modulus; a second prime (2 less than the
@@ -142,6 +135,7 @@ _csi_hash_table_init (csi_hash_table_t *hash_table,
return _csi_error (CAIRO_STATUS_NO_MEMORY);
hash_table->live_entries = 0;
+ hash_table->used_entries = 0;
hash_table->iterating = 0;
return CSI_STATUS_SUCCESS;
@@ -202,56 +196,93 @@ _csi_hash_table_lookup_unique_key (csi_hash_table_t *hash_table,
}
/**
- * _csi_hash_table_resize:
+ * _csi_hash_table_manage:
* @hash_table: a hash table
*
* Resize the hash table if the number of entries has gotten much
* bigger or smaller than the ideal number of entries for the current
- * size.
+ * size, or control the number of dead entries by moving the entries
+ * within the table.
*
* Return value: %CAIRO_STATUS_SUCCESS if successful or
* %CAIRO_STATUS_NO_MEMORY if out of memory.
**/
static csi_status_t
-_csi_hash_table_resize (csi_hash_table_t *hash_table)
+_csi_hash_table_manage (csi_hash_table_t *hash_table)
{
csi_hash_table_t tmp;
- unsigned long new_size, i;
+ csi_boolean_t realloc = TRUE;
+ unsigned long i;
- /* This keeps the hash table between 25% and 50% full. */
+ /* This keeps the size of the hash table between 2 and approximately 8
+ * times the number of live entries and keeps the proportion of free
+ * entries (search-terminations) > 25%.
+ */
unsigned long high = hash_table->arrangement->high_water_mark;
unsigned long low = high >> 2;
-
- if (hash_table->live_entries >= low && hash_table->live_entries <= high)
- return CAIRO_STATUS_SUCCESS;
+ unsigned long max_used = high + high / 2;
tmp = *hash_table;
if (hash_table->live_entries > high) {
tmp.arrangement = hash_table->arrangement + 1;
/* This code is being abused if we can't make a table big enough. */
- } else { /* hash_table->live_entries < low */
- /* Can't shrink if we're at the smallest size */
- if (hash_table->arrangement == &hash_table_arrangements[0])
- return CAIRO_STATUS_SUCCESS;
+ } else if (hash_table->live_entries < low &&
+ /* Can't shrink if we're at the smallest size */
+ hash_table->arrangement != &hash_table_arrangements[0])
+ {
tmp.arrangement = hash_table->arrangement - 1;
}
+ else if (hash_table->used_entries > max_used)
+ {
+ /* Clean out dead entries to prevent lookups from becoming too slow. */
+ for (i = 0; i < hash_table->arrangement->size; ++i) {
+ if (ENTRY_IS_DEAD (hash_table->entries[i]))
+ hash_table->entries[i] = NULL;
+ }
+ hash_table->used_entries = hash_table->live_entries;
+
+ /* There is no need to reallocate but some entries may need to be
+ * moved. Typically the proportion of entries needing to be moved is
+ * small, but, if the moving should leave a large number of dead
+ * entries, they will be cleaned out next time this code is
+ * executed. */
+ realloc = FALSE;
+ }
+ else
+ {
+ return CAIRO_STATUS_SUCCESS;
+ }
- new_size = tmp.arrangement->size;
- tmp.entries = calloc (new_size, sizeof (csi_hash_entry_t*));
- if (tmp.entries == NULL)
- return _csi_error (CAIRO_STATUS_NO_MEMORY);
+ if (realloc) {
+ tmp.entries = calloc (tmp.arrangement->size,
+ sizeof (csi_hash_entry_t*));
+ if (tmp.entries == NULL)
+ return _csi_error (CAIRO_STATUS_NO_MEMORY);
+
+ hash_table->used_entries = 0;
+ }
for (i = 0; i < hash_table->arrangement->size; ++i) {
- if (ENTRY_IS_LIVE (hash_table->entries[i])) {
- *_csi_hash_table_lookup_unique_key (&tmp, hash_table->entries[i])
- = hash_table->entries[i];
+ csi_hash_entry_t *entry, **pos;
+
+ entry = hash_table->entries[i];
+ if (ENTRY_IS_LIVE (entry)) {
+ hash_table->entries[i] = DEAD_ENTRY;
+
+ pos = _csi_hash_table_lookup_unique_key (&tmp, entry);
+ if (ENTRY_IS_FREE (*pos))
+ hash_table->used_entries++;
+
+ *pos = entry;
}
}
- free (hash_table->entries);
- hash_table->entries = tmp.entries;
- hash_table->arrangement = tmp.arrangement;
+ if (realloc) {
+ free (hash_table->entries);
+ hash_table->entries = tmp.entries;
+ hash_table->arrangement = tmp.arrangement;
+ }
return CAIRO_STATUS_SUCCESS;
}
@@ -332,18 +363,22 @@ _csi_hash_table_insert (csi_hash_table_t *hash_table,
csi_hash_entry_t *key_and_value)
{
csi_status_t status;
+ csi_hash_entry_t **entry;
hash_table->live_entries++;
- status = _csi_hash_table_resize (hash_table);
+ status = _csi_hash_table_manage (hash_table);
if (_csi_unlikely (status)) {
/* abort the insert... */
hash_table->live_entries--;
return status;
}
- *_csi_hash_table_lookup_unique_key (hash_table,
- key_and_value) = key_and_value;
+ entry = _csi_hash_table_lookup_unique_key (hash_table,
+ key_and_value);
+ if (ENTRY_IS_FREE (*entry))
+ hash_table->used_entries++;
+ *entry = key_and_value;
return CAIRO_STATUS_SUCCESS;
}
@@ -402,7 +437,7 @@ _csi_hash_table_remove (csi_hash_table_t *hash_table,
* memory to shrink the hash table. It does leave the table in a
* consistent state, and we've already succeeded in removing the
* entry, so we don't examine the failure status of this call. */
- _csi_hash_table_resize (hash_table);
+ _csi_hash_table_manage (hash_table);
}
}
@@ -443,6 +478,6 @@ _csi_hash_table_foreach (csi_hash_table_t *hash_table,
if (--hash_table->iterating == 0) {
/* Should we fail to shrink the hash table, it is left unaltered,
* and we don't need to propagate the error status. */
- _csi_hash_table_resize (hash_table);
+ _csi_hash_table_manage (hash_table);
}
}
diff --git a/util/cairo-script/cairo-script-private.h b/util/cairo-script/cairo-script-private.h
index 772be4c..d177a29 100644
--- a/util/cairo-script/cairo-script-private.h
+++ b/util/cairo-script/cairo-script-private.h
@@ -340,6 +340,7 @@ struct _csi_hash_table {
csi_hash_entry_t **entries;
unsigned long live_entries;
+ unsigned long used_entries;
unsigned long iterating; /* Iterating, no insert, no resize */
};
commit 4ccfd474a36f482adcab49a8d38742121817b47e
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Sat Jun 6 13:32:21 2009 +0100
[perf] Switch to using clock_gettime()
Try using clock_gettime() for a high resolution stable time source in
preference to the potentially unstable TSC.
diff --git a/build/configure.ac.system b/build/configure.ac.system
index 2ee0cc4..341f5e9 100644
--- a/build/configure.ac.system
+++ b/build/configure.ac.system
@@ -60,8 +60,13 @@ dnl Check for socket support for any2ppm daemon
AC_CHECK_HEADERS([fcntl.h unistd.h signal.h sys/stat.h sys/socket.h sys/poll.h sys/un.h])
dnl check for CPU affinity support
-AC_CHECK_HEADERS([sched.h],
- [AC_CHECK_FUNCS([sched_getaffinity])])
+AC_CHECK_HEADERS([sched.h], [AC_CHECK_FUNCS([sched_getaffinity])])
+
+dnl check for clock_gettime() support
+save_LIBS="$LIBS"
+LIBS="$LIBS $RT_LIBS"
+AC_CHECK_HEADERS([time.h], [AC_CHECK_FUNCS([clock_gettime])])
+LIBS="$save_LIBS"
dnl check for GNU-extensions to fenv
AC_CHECK_HEADER(fenv.h,
diff --git a/perf/cairo-perf-posix.c b/perf/cairo-perf-posix.c
index 8bc4e09..68b78d0 100644
--- a/perf/cairo-perf-posix.c
+++ b/perf/cairo-perf-posix.c
@@ -55,7 +55,10 @@
#define _XOPEN_SOURCE 600 /* for round() */
+#include "config.h"
+
#include <signal.h>
+#include <time.h>
#include <sys/time.h>
#include <unistd.h>
#ifdef _POSIX_PRIORITY_SCHEDULING
@@ -66,13 +69,22 @@
/* timers */
+#if defined(HAVE_CLOCK_GETTIME)
+#if defined(CLOCK_MONOTONIC_RAW)
+#define CLOCK CLOCK_MONOTONIC_RAW
+#elif defined(CLOCK_MONOTONIC)
+#define CLOCK CLOCK_MONOTONIC
+#endif
+#endif
+
+#if ! defined(CLOCK)
#if defined(__i386__) || defined(__amd64__)
static inline cairo_perf_ticks_t
oil_profile_stamp_rdtsc (void)
{
- unsigned a, d;
- __asm__ __volatile__("rdtsc" : "=a" (a), "=d" (d));
- return ((uint64_t)a) | (((uint64_t)d) << 32);
+ unsigned a, d;
+ __asm__ __volatile__("rdtsc" : "=a" (a), "=d" (d));
+ return ((uint64_t)a) | (((uint64_t)d) << 32);
}
#define OIL_STAMP oil_profile_stamp_rdtsc
#endif
@@ -118,10 +130,13 @@ oil_profile_stamp_s390(void)
}
#define OIL_STAMP oil_profile_stamp_s390
#endif
+#endif
-typedef struct _cairo_perf_timer
-{
-#ifdef OIL_STAMP
+typedef struct _cairo_perf_timer {
+#if defined(CLOCK)
+ struct timespec tv_start;
+ struct timespec tv_stop;
+#elif defined(OIL_STAMP)
cairo_perf_ticks_t start;
cairo_perf_ticks_t stop;
#else
@@ -143,10 +158,14 @@ cairo_perf_timer_set_synchronize (cairo_perf_timer_synchronize_t synchronize,
}
void
-cairo_perf_timer_start (void) {
+cairo_perf_timer_start (void)
+{
if (cairo_perf_timer_synchronize)
cairo_perf_timer_synchronize (cairo_perf_timer_synchronize_closure);
-#ifdef OIL_STAMP
+
+#if defined(CLOCK)
+ clock_gettime (CLOCK, &timer.tv_start);
+#elif defined(OIL_STAMP)
timer.start = OIL_STAMP ();
#else
gettimeofday (&timer.tv_start, NULL);
@@ -154,10 +173,14 @@ cairo_perf_timer_start (void) {
}
void
-cairo_perf_timer_stop (void) {
+cairo_perf_timer_stop (void)
+{
if (cairo_perf_timer_synchronize)
cairo_perf_timer_synchronize (cairo_perf_timer_synchronize_closure);
-#ifdef OIL_STAMP
+
+#if defined(CLOCK)
+ clock_gettime (CLOCK, &timer.tv_stop);
+#elif defined(OIL_STAMP)
timer.stop = OIL_STAMP ();
#else
gettimeofday (&timer.tv_stop, NULL);
@@ -165,22 +188,32 @@ cairo_perf_timer_stop (void) {
}
cairo_perf_ticks_t
-cairo_perf_timer_elapsed (void) {
+cairo_perf_timer_elapsed (void)
+{
cairo_perf_ticks_t ticks;
-#ifdef OIL_STAMP
- ticks = (timer.stop - timer.start);
+#if defined(CLOCK)
+ ticks = timer.tv_stop.tv_sec - timer.tv_start.tv_sec;
+ ticks *= 1000000000;
+ ticks += timer.tv_stop.tv_nsec - timer.tv_start.tv_nsec;
+#elif defined(OIL_STAMP)
+ ticks = timer.stop - timer.start;
#else
- ticks = (timer.tv_stop.tv_sec - timer.tv_start.tv_sec) * 1000000;
- ticks += (timer.tv_stop.tv_usec - timer.tv_start.tv_usec);
+ ticks = timer.tv_stop.tv_sec - timer.tv_start.tv_sec;
+ ticks *= 1000000;
+ ticks += timer.tv_stop.tv_usec - timer.tv_start.tv_usec;
#endif
return ticks;
}
cairo_perf_ticks_t
-cairo_perf_ticks_per_second (void) {
-#ifdef OIL_STAMP
+cairo_perf_ticks_per_second (void)
+{
+#if defined(CLOCK)
+ /* For clock_gettime() the units are nano-seconds */
+ return 1000000000;
+#elif defined(OIL_STAMP)
static cairo_perf_ticks_t tps = 0;
/* XXX: This is obviously not stable in light of changing CPU speed. */
if (tps == 0) {
@@ -197,7 +230,7 @@ cairo_perf_ticks_per_second (void) {
}
return tps;
#else
- /* For gettimeofday the units are micro-seconds */
+ /* For gettimeofday() the units are micro-seconds */
return 1000000;
#endif
}
@@ -205,7 +238,8 @@ cairo_perf_ticks_per_second (void) {
/* yield */
void
-cairo_perf_yield (void) {
+cairo_perf_yield (void)
+{
#ifdef _POSIX_PRIORITY_SCHEDULING
sched_yield ();
#endif
More information about the cairo-commit
mailing list