Hi all,

I am new to this list and I would like to help with the GEGL development. I am a programmer and a computer graphics enthusiast. I started to look into the GEGL/BABL code base and have been able to make some improvements in babl database code that speed things up a bit, without loss of readability. Should you guys be interested I can post the patch to this list and I can try to look into things further. If you have other ideas as to where any help might be needed I'll be glad to help.

Regards, Jan

On 19:07, Sun 09 Mar 08, Martin Nordholts wrote:

Hi Jan

We're absolutely interested in your contributions! Eagerly awaiting the patch :)

Best regards,
Martin Nordholts

Glad to hear it :) So here is the patch. Essentially, it implements coalesced hashing as BablHashTable structure and uses it as the babl database data structure. The code is not long and is quite self-explanatory I believe, although I wouldn't mind adding a few comments if needed.

Regards, Jan

Index: babl/babl-util.c
=================================================================== --- babl/babl-util.c (revision 290)
+++ babl/babl-util.c (working copy)
@@ -22,6 +22,287 @@
#include
#include "babl-memory.h"
#include "babl-internal.h"
+#include "babl-util.h"
+
+#define UTIL_INITIAL_LIST_SIZE 0x7F +#define UTIL_INITIAL_HT_MASK 0x7F +
+/* static functions declarations */ +static inline int
+hash_by_name (BablHashTable *htab,
+ const char *str);
+
+static inline int
+hash_by_id (BablHashTable *htab,
+ int id);
+
+static inline int
+hash_insert (BablHashTable *htab,
+ Babl *item);
+
+static void
+hash_rehash (BablHashTable *htab);
+
+/* BablList functions */
+
+BablList *
+babl_list_init (void)
+{
+ BablList *list = babl_calloc (sizeof (BablList), 1); +
+ list->size = UTIL_INITIAL_LIST_SIZE; + list->count = 0;
+ list->items = NULL;
+ if (list->size)
+ {
+ list->items = babl_calloc (sizeof (BablInstance *), list->size); + }
+
+ return list;
+}
+
+void
+babl_list_destroy (BablList *list)
+{
+ babl_assert(list);
+
+ babl_free (list->items);
+ babl_free (list);
+}
+
+void
+babl_list_insert (BablList *list,
+ Babl *item)
+{
+ babl_assert(list);
+ babl_assert(BABL_IS_BABL(item));
+
+ if (list->size < list->count + 1) + {
+ Babl **new_items;
+
+ new_items = babl_realloc (list->items, (list->size * 2) * sizeof (BablInstance *)); + babl_assert (new_items);
+ list->items = new_items;
+ memset (list->items + list->size, 0, list->size * sizeof (BablInstance *)); + list->size *= 2;
+ }
+ list->items[list->count++] = item; +}
+
+void
+babl_list_each_NEW (BablList *list, + BablEachFunction each_fun, + void *user_data) +{
+ int i;
+
+ babl_assert(list);
+ babl_assert(each_fun);
+
+ for (i = 0; i < list->count; i++) + {
+ if (list->items[i])
+ {
+ if (each_fun ((Babl *) list->items[i], user_data)) + break;
+ }
+ }
+}
+
+/* BablHashTable functions */
+
+
+inline int
+babl_hash_by_str (BablHashTable *htab, + const char *str) +{
+ int hash = 0;
+
+ while (*str)
+ {
+ hash += *str++;
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ }
+ hash += (hash << 3);
+ hash ^= (hash >> 11);
+ hash += (hash << 15);
+
+ return (hash & htab->mask);
+}
+
+inline int
+babl_hash_by_int (BablHashTable *htab, + int id) +{
+ int hash = 0;
+ int i;
+
+ for (i = 0; i < sizeof (int); i++) + {
+ hash += id & 0xFF;
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ id >>= 8;
+ }
+ hash += (hash << 3);
+ hash ^= (hash >> 11);
+ hash += (hash << 15);
+
+ return (hash & htab->mask);
+}
+
+static inline int
+hash_insert (BablHashTable *htab,
+ Babl *item)
+{
+ int hash = htab->hash_func(htab, item); +
+ if (htab->data_table[hash] == NULL) + {
+ /* create new chain */
+ htab->data_table[hash] = item; + }
+ else
+ {
+ int it, oit, cursor = 0;
+
+ while ((cursor < (htab->mask + 1)) && (htab->data_table[cursor] != NULL)) + ++cursor;
+
+ htab->data_table[cursor] = item; +
+ for (oit = hash, it = htab->chain_table[oit]; it != -1; oit = it, it = htab->chain_table[oit]) + ;
+ htab->chain_table[oit] = cursor; + }
+
+ htab->count++;
+ return 0;
+}
+
+static void
+hash_rehash (BablHashTable *htab)
+{
+ Babl *item;
+ int i;
+ BablHashTable *nhtab = babl_calloc (sizeof (BablHashTable), 1); +
+ nhtab->data_table = NULL;
+ nhtab->chain_table = NULL;
+ nhtab->mask = (htab->mask << 1) + 1; + nhtab->count = 0;
+ nhtab->hash_func = htab->hash_func; + nhtab->find_func = htab->find_func; + if (nhtab->mask)
+ {
+ nhtab->data_table = babl_calloc (sizeof (BablInstance *), babl_hash_size(nhtab)); + nhtab->chain_table = babl_malloc (sizeof (int *) * babl_hash_size(nhtab)); + memset (nhtab->chain_table, -1, sizeof (int) * babl_hash_size(nhtab)); + }
+
+ for (i = 0; i < babl_hash_size (htab); i++) + {
+ item = htab->data_table[i];
+ babl_hash_insert (nhtab, item); + }
+
+ htab->mask = nhtab->mask;
+ babl_free (htab->data_table);
+ babl_free (htab->chain_table);
+ htab->data_table = nhtab->data_table; + htab->chain_table = nhtab->chain_table; + babl_free (nhtab);
+}
+
+inline int
+babl_hash_size (BablHashTable *htab) +{
+ return htab->mask + 1;
+}
+
+BablHashTable *
+babl_hash_init (BablHashValFunction hfunc, + BablHashFindFunction ffunc) +{
+ BablHashTable *htab;
+
+ babl_assert(hfunc);
+ babl_assert(ffunc);
+
+ htab = babl_calloc (sizeof (BablHashTable), 1); + babl_assert (htab);
+
+ htab->data_table = NULL;
+ htab->chain_table = NULL;
+ htab->mask = UTIL_INITIAL_HT_MASK; + htab->count = 0;
+ htab->hash_func = hfunc;
+ htab->find_func = ffunc;
+ if (htab->mask)
+ {
+ htab->data_table = babl_calloc (sizeof (BablInstance *), babl_hash_size(htab)); + htab->chain_table = babl_malloc (sizeof (int *) * babl_hash_size(htab)); + memset (htab->chain_table, -1, sizeof (int) * babl_hash_size(htab)); + }
+
+ return htab;
+}
+
+void
+babl_hash_destroy (BablHashTable *htab) +{
+ babl_assert (htab);
+
+ babl_free (htab->data_table);
+ babl_free (htab->chain_table);
+ babl_free (htab);
+}
+
+int
+babl_hash_insert (BablHashTable *htab, + Babl *item) +{
+ babl_assert (htab);
+ babl_assert (BABL_IS_BABL(item)); +
+ if (babl_hash_size (htab) < htab->count + 1) + hash_rehash (htab);
+ return hash_insert (htab, item);
+}
+
+Babl *
+babl_hash_find (BablHashTable *htab, + int hash, + void *data) +{
+ int it;
+ Babl *item;
+
+ babl_assert (htab);
+
+ it = hash;
+ item = htab->data_table[it];
+
+ if (!item)
+ return NULL;
+
+ for (;;)
+ {
+ if (htab->find_func (item, data)) + return item;
+ it = htab->chain_table[it];
+ if (it == -1)
+ break;
+ item = htab->data_table[it];
+ }
+
+ return NULL;
+}
+
+
+/* Utils */

static int list_length (void **list) {
Index: babl/babl-util.h
=================================================================== --- babl/babl-util.h (revision 290)
+++ babl/babl-util.h (working copy)
@@ -21,13 +21,89 @@

#include

-void babl_add_ptr_to_list (void ***list, - void *new); +typedef struct _BablHashTable BablHashTable; +typedef struct _BablList BablList;
+
+typedef int (*BablHashValFunction) (BablHashTable *htab, Babl *item); +typedef int (*BablHashFindFunction) (Babl *item, void *data); +
+typedef struct _BablList
+{
+ int count;
+ int size;
+ Babl **items;
+} _BablList;
+
+typedef struct _BablHashTable
+{
+ Babl **data_table; + int *chain_table; + int mask;
+ int count;
+ BablHashValFunction hash_func;
+ BablHashFindFunction find_func;
+} _BablHashTable;
+
+
+/* BablList functions */
+
+BablList *
+babl_list_init (void);
+
+void
+babl_list_destroy (BablList *list); +
+void
+babl_list_insert (BablList *list,
+ Babl *item);
+
+void
+babl_list_each_NEW (BablList *list, + BablEachFunction each_fun, + void *user_data);
void
babl_list_each (void **list, - BablEachFunction each_fun, - void *user_data); + BablEachFunction each_fun, + void *user_data); +
+void
+babl_add_ptr_to_list (void ***list, + void *new); +
+
+
+/* BablHashTable functions */
+
+BablHashTable *
+babl_hash_init (BablHashValFunction hfunc, + BablHashFindFunction ffunc); +
+inline int
+babl_hash_by_str (BablHashTable *htab, + const char *str); +
+inline int
+babl_hash_by_int (BablHashTable *htab, + int id); +
+inline int
+babl_hash_size (BablHashTable *htab); +
+int
+babl_hash_insert (BablHashTable *htab, + Babl *item); +
+Babl *
+babl_hash_find (BablHashTable *htab, + int hash, + void *data); +
+void
+babl_hash_destroy (BablHashTable *htab); +
+
+/* Utils */

long
babl_ticks (void);
Index: babl/babl-db.c
=================================================================== --- babl/babl-db.c (revision 290)
+++ babl/babl-db.c (working copy)
@@ -21,106 +21,90 @@
#include
#include "babl-internal.h"

-#define DB_INITIAL_SIZE 16
-#define DB_INCREMENT_SIZE 16
-
-static inline int hash (const char *str) +static int
+db_find_by_name (Babl *item, void *data) {
- int ret = 0;
- int i = 1;
-
- while (*str)
- ret = (ret + (i++ * (*str++ & 31))) % (HASH_TABLE_SIZE - 1); - return ret;
+ if (!strcmp (item->instance.name, (char *) data)) + return 1;
+ return 0;
}

-
-Babl *
-babl_db_find (BablDb *db,
- const char *name)
+static int
+db_find_by_id (Babl *item, void *data) {
- Babl *ret = babl_db_exist (db, 0, name); + if (item->instance.id == *((int *) data)) + return 1;
+ return 0;
+}

- if (!ret)
- {
- const char *sample_type = "unknwon"; -
- if (db->items[0])
- sample_type = babl_class_name (db->items[0]->class_type); - babl_log ("failed (query performed on a %s database)", sample_type); - }
- return ret;
+static int
+db_hash_by_name (BablHashTable *htab, Babl *item) +{
+ return babl_hash_by_str (htab, item->instance.name); }

+static int
+db_hash_by_id (BablHashTable *htab, Babl *item) +{
+ return babl_hash_by_int (htab, item->instance.id); +}

BablDb *
babl_db_init (void)
{
BablDb *db = babl_calloc (sizeof (BablDb), 1);
- db->size = DB_INITIAL_SIZE;
- db->count = 0;
- db->items = NULL;
- if (db->size)
- {
- db->items = babl_calloc (sizeof (BablInstance *), db->size); - }
- return db;
-}
+ db->name_hash = babl_hash_init (db_hash_by_name, db_find_by_name); + db->id_hash = babl_hash_init (db_hash_by_id, db_find_by_id); + db->babl_list = babl_list_init ();
-
-int
-babl_db_count (BablDb *db)
-{
- return db->count;
+ return db;
}

void
babl_db_destroy (BablDb *db)
{
- babl_free (db->items);
+ babl_assert (db);
+
+ babl_hash_destroy (db->name_hash); + babl_hash_destroy (db->id_hash);
+ babl_list_destroy (db->babl_list); babl_free (db);
}

Babl *
-babl_db_insert (BablDb *db,
- Babl *item)
+babl_db_find (BablDb *db,
+ const char *name)
{
- Babl *collision;
-
- babl_assert (db && item);
- babl_assert (item->instance.name); -
- collision = babl_db_exist (db, item->instance.id, item->instance.name); -
- if (collision)
- return collision;
+ return babl_hash_find (db->name_hash, babl_hash_by_str (db->name_hash, name), (void *) name); +}

- if (db->count + 1 > db->size) /* must reallocate storage */ - {
- Babl **new_items;
+int
+babl_db_count (BablDb *db)
+{
+ return db->babl_list->count;
+}

- new_items = babl_realloc (db->items, (db->size + DB_INCREMENT_SIZE) * sizeof (BablInstance *)); - babl_assert (new_items);
+Babl *
+babl_db_insert (BablDb *db,
+ Babl *item)
+{

- db->items = new_items;
+ Babl *found = babl_db_exist (db, item->instance.id, item->instance.name);
- /* null out the currently unused portions of memory */ - memset (db->items + db->size, 0, DB_INCREMENT_SIZE * sizeof (Babl *)); - db->size += DB_INCREMENT_SIZE; - }
+ if (found)
+ return found;

- {
- int key = hash (item->instance.name); - if (db->hash[key] == NULL)
- db->hash[key] = item;
- }
- db->items[db->count++] = item;
+ if (item->instance.id)
+ babl_hash_insert (db->id_hash, item); + babl_hash_insert (db->name_hash, item); + babl_list_insert (db->babl_list, item);
/* this point all registered items pass through, a nice * place to brand them with where the item came from. */ item->instance.creator = babl_extender (); return item;
+
}

void
@@ -128,84 +112,31 @@ babl_db_each (BablDb *db, BablEachFunction each_fun, void *user_data) {
- int i;
-
- for (i = 0; i < db->count; i++)
- {
- if (db->items[i])
- {
- if (each_fun ((Babl *) db->items[i], user_data)) - break;
- }
- }
-}
-
-static inline void
-babl_db_each_inline (BablDb *db, - BablEachFunction each_fun, - void *user_data) -{
- int i;
-
- for (i = 0; i < db->count; i++)
- {
- if (db->items[i])
- {
- if (each_fun ((Babl *) db->items[i], user_data)) - break;
- }
- }
-}
-
-typedef struct BablDbExistData
-{
- int id;
- const char *name;
- Babl *ret;
-} BablDbExistData;
-
-static int
-babl_db_each_exist (Babl *babl,
- void *void_data) -{
- BablDbExistData *data = void_data; -
- if (data->id && data->id == babl->instance.id) - {
- data->ret = babl;
- return 1; /* stop iterating */ - }
- else if (data->name && !strcmp (babl->instance.name, data->name)) - {
- data->ret = babl;
- return 1; /* stop iterating */ - }
- return 0; /* continue iterating */ + babl_list_each_NEW (db->babl_list, each_fun, user_data); }

+
Babl *
babl_db_exist (BablDb *db,
int id,
const char *name)
{
- Babl *ret = NULL;
-
- if (name)
- ret = db->hash[hash (name)];
- if (ret &&
- name[0] == ret->instance.name[0] && - !strcmp (name, ret->instance.name)) - return ret;
-
- {
- BablDbExistData data;
-
- data.id = id;
- data.name = name;
- data.ret = NULL;
+ if (id)
+ return babl_hash_find (db->id_hash, babl_hash_by_int (db->id_hash, id), &id); + return babl_hash_find (db->name_hash, babl_hash_by_str (db->name_hash, name), (void *) name); +}

- babl_db_each_inline (db, babl_db_each_exist, &data); +Babl *
+babl_db_exist_by_id (BablDb *db,
+ int id)
+{
+ return babl_hash_find (db->id_hash, babl_hash_by_int (db->id_hash, id), &id); +}

- return data.ret;
- }
+Babl *
+babl_db_exist_by_name (BablDb *db, + const char *name) +{
+ return babl_hash_find (db->name_hash, babl_hash_by_str (db->name_hash, name), name); }
+
Index: babl/babl-fish.c
=================================================================== --- babl/babl-fish.c (revision 290)
+++ babl/babl-fish.c (working copy)
@@ -62,9 +62,9 @@ go_fishing (const Babl *source, BablDb *db = babl_fish_db ();
int i;

- for (i=0; icount; i++)
+ for (i=0; ibabl_list->count; i++) {
- Babl *item = db->items[i];
+ Babl *item = db->babl_list->items[i]; if ((void *) source == (void *) item->fish.source && (void *) destination == (void *) item->fish.destination && (item->class_type == BABL_FISH_PATH || /* accept only paths */ Index: babl/babl-db.h
=================================================================== --- babl/babl-db.h (revision 290)
+++ babl/babl-db.h (working copy)
@@ -19,20 +19,20 @@
#ifndef _DB_H
#define _DB_H

+#include "babl-util.h"
+
#ifndef _BABL_INTERNAL_H
#error babl-db.h is only to be included after babl-internal.h #endif

-typedef struct _BablDb BablDb;

-#define HASH_TABLE_SIZE 128
-typedef struct _BablDb
+typedef struct BablDb
{
- Babl *hash [HASH_TABLE_SIZE];
- int size;
- int count;
- Babl **items;
-} _BablDb;
+ BablHashTable *name_hash;
+ BablHashTable *id_hash;
+ BablList *babl_list;
+} BablDb;
+

BablDb * babl_db_init (void);
void babl_db_destroy (BablDb *db); @@ -48,4 +48,12 @@ Babl * babl_db_exist (BablDb Babl * babl_db_find (BablDb *db, const char *name);
+Babl *
+babl_db_exist_by_id (BablDb *db,
+ int id);
+
+Babl *
+babl_db_exist_by_name (BablDb *db, + const char *name); +
#endif

On 17:55, Mon 10 Mar 08, Martin Nordholts wrote:

That looks very interesting. Do you think you could provide some benchmarking data of the performance improvements in variuos situations? It would be useful to have

Hi,

I used babl/tests/babl_fish_path_dhtml as a simple benchmark. Here are running times of babl_fish_path_dhtml w/o and w/ the patch applied:

jheller@voyager ~/projects/gegl/babl/babl/tests $ time ./babl_fish_path_dhtml > babl_fish_path_0.0.20.html

real 0m10.463s user 0m9.441s
sys 0m0.040s

jheller@voyager ~/projects/gegl/babl-patch/babl/tests $ time ./babl_fish_path_dhtml > babl_fish_path_patch.html

real 0m3.844s user 0m3.416s
sys 0m0.048s

Here are the resulting HTML files:

http://www.ms.mff.cuni.cz/~hellj1am/WWW/babl_fish_path_0.0.20.html http://www.ms.mff.cuni.cz/~hellj1am/WWW/babl_fish_path_patch.html

Such a dramatic performance gain is not to be expected from any practical usage of the babl library, since the database code is not as heavily used.

A simple 512x512 16-bit/color RGBA PNG image load/save test using gegl gives following results for runs w/o and w/ the patch. I took the respective best results from several tries:

W/O
real 0m6.367s
user 0m3.476s
sys 0m0.168s

W
real 0m2.930s
user 0m2.400s
sys 0m0.096s

I hope these results give a better idea about the performance of the changes.

Regards,
Jan

On 21:09, Mon 10 Mar 08, Sven Neumann wrote:

I would prefer if this functionality could be added in new files babl-list.[ch] and babl-hash-table.[ch]. Also the hash-table functions should be prefixed with babl_hash_table_ instead of just babl_hash_ as we should keep the babl_hash prefix for hash functions. Then I don't

Such changes can be easily and happily arranged in case the patch would make it to the babl.

understand the purpose of babl_list_each_NEW(). This is just temporary, isn't it?

Yes, that is correct. There is an another implementation of the list data structure already present in the babl with a colliding function name. The next step after the patch would be migrating the code to the new implementation of the list data structure, which would not necessarily improve speed of the code, however, this would IMHO improve readability and maintainability a bit.

Regards, Jan