Re: [Gegl-developer] Hi, need any help?
Jan Heller wrote: 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: Hello again Sorry for being slow here This is pretty impressive results I must say. I have created a bug report about it in bugzilla [1] so we can track the patch while we integrate it into Babl. Best regards, Martin Nordholts [1] Bug 523507 – [PATCH] New database backend based on a coalesced hashtable http://bugzilla.gnome.org/show_bug.cgi?id=523507 ___ Gegl-developer mailing list Gegl-developer@lists.XCF.Berkeley.EDU https://lists.XCF.Berkeley.EDU/mailman/listinfo/gegl-developer
Re: [Gegl-developer] Hi, need any help?
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: [EMAIL PROTECTED] ~/projects/gegl/babl/babl/tests $ time ./babl_fish_path_dhtml babl_fish_path_0.0.20.html real0m10.463s user0m9.441s sys 0m0.040s [EMAIL PROTECTED] ~/projects/gegl/babl-patch/babl/tests $ time ./babl_fish_path_dhtml babl_fish_path_patch.html real0m3.844s user0m3.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 real0m6.367s user0m3.476s sys 0m0.168s W real0m2.930s user0m2.400s sys 0m0.096s I hope these results give a better idea about the performance of the changes. Regards, Jan ___ Gegl-developer mailing list Gegl-developer@lists.XCF.Berkeley.EDU https://lists.XCF.Berkeley.EDU/mailman/listinfo/gegl-developer
Re: [Gegl-developer] Hi, need any help?
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 ___ Gegl-developer mailing list Gegl-developer@lists.XCF.Berkeley.EDU https://lists.XCF.Berkeley.EDU/mailman/listinfo/gegl-developer
Re: [Gegl-developer] Hi, need any help?
Jan Heller wrote: 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 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 Best regards, Martin Nordholts ___ Gegl-developer mailing list Gegl-developer@lists.XCF.Berkeley.EDU https://lists.XCF.Berkeley.EDU/mailman/listinfo/gegl-developer
Re: [Gegl-developer] Hi, need any help?
Hi, On Mon, 2008-03-10 at 00:35 +0100, Jan Heller wrote: 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. Thanks for the patch. Here are some comments that I collected when reading through the patch: 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 understand the purpose of babl_list_each_NEW(). This is just temporary, isn't it? Oh, and if Pippin wouldn't object against making babl depend on glib, we wouldn't have to duplicate all this code... Sven ___ Gegl-developer mailing list Gegl-developer@lists.XCF.Berkeley.EDU https://lists.XCF.Berkeley.EDU/mailman/listinfo/gegl-developer
Re: [Gegl-developer] Hi, need any help?
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 math.h
#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 *
