summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJérémy Zurcher <jeremy@asynk.ch>2013-01-04 08:41:47 +0000
committerCarsten Haitzler <raster@rasterman.com>2013-01-04 08:41:47 +0000
commit1424ac7d4d211fab7d3dcb0faeeb74ca641ca0f6 (patch)
tree9c85c5684297ae5f95d31ae46b0012d2233b69d1
parent9b252e40d43f805479f79d3a78b417d2859c6dc4 (diff)
From: Jérémy Zurcher <jeremy@asynk.ch>
Subject: [E-devel] 2 steps eina_share_common_del speed up builtin node is never unlinked even if empty, always is the last of the queue, so that it can be used to get a pointer to head. cost: never unlink or promote builtin node. benefit: no need to hash and search rbtree to unlink an empty node, only to remove an empty head. store full hash in Eina_Share_Common_Head, so we only hash once use 8 lower bits as node hash, use next 8 bits as bucket index. cost: have to apply 0xFF mask on hash in rbtree callbacks. benefit: no need to hash when removing an empty head. SVN revision: 82161
-rw-r--r--ChangeLog4
-rw-r--r--NEWS1
-rw-r--r--src/lib/eina/eina_share_common.c103
-rw-r--r--src/lib/eina/eina_stringshare.c25
4 files changed, 80 insertions, 53 deletions
diff --git a/ChangeLog b/ChangeLog
index cb77d72..d78204c 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,7 @@
12013-01-04 Jérémy Zurcher
2
3 * Improve eina_share string del speed by a maybe 5-15%.
4
12013-01-03 Gustavo Sverzut Barbieri (k-s) 52013-01-03 Gustavo Sverzut Barbieri (k-s)
2 6
3 * Add eina_alloc.h to Eina.h to define alloca() 7 * Add eina_alloc.h to Eina.h to define alloca()
diff --git a/NEWS b/NEWS
index f46081e..185c977 100644
--- a/NEWS
+++ b/NEWS
@@ -73,6 +73,7 @@ Improvements:
73 * all efl object-freeing functions now take NULL without crashing or erroring 73 * all efl object-freeing functions now take NULL without crashing or erroring
74 * use Eina_File in webp, gif, tiff, png and eet loader 74 * use Eina_File in webp, gif, tiff, png and eet loader
75 * Eina.h includes eina_alloca.h/alloca.h to define alloca() 75 * Eina.h includes eina_alloca.h/alloca.h to define alloca()
76 * Improved eina share del speed.
76 77
77Fixes: 78Fixes:
78 * Fix PPC (big endian) image codec bug. 79 * Fix PPC (big endian) image codec bug.
diff --git a/src/lib/eina/eina_share_common.c b/src/lib/eina/eina_share_common.c
index 29c9f47..0dbf37d 100644
--- a/src/lib/eina/eina_share_common.c
+++ b/src/lib/eina/eina_share_common.c
@@ -88,6 +88,8 @@
88 88
89#define EINA_SHARE_COMMON_BUCKETS 256 89#define EINA_SHARE_COMMON_BUCKETS 256
90#define EINA_SHARE_COMMON_MASK 0xFF 90#define EINA_SHARE_COMMON_MASK 0xFF
91#define EINA_SHARE_COMMON_BUCKET_IDX(h) ((h >> 8) & EINA_SHARE_COMMON_MASK)
92#define EINA_SHARE_COMMON_NODE_HASH(h) (h & EINA_SHARE_COMMON_MASK)
91 93
92static const char EINA_MAGIC_SHARE_STR[] = "Eina Share"; 94static const char EINA_MAGIC_SHARE_STR[] = "Eina Share";
93static const char EINA_MAGIC_SHARE_HEAD_STR[] = "Eina Share Head"; 95static const char EINA_MAGIC_SHARE_HEAD_STR[] = "Eina Share Head";
@@ -113,8 +115,13 @@ static int _eina_share_common_count = 0;
113 } \ 115 } \
114 } while (0) 116 } while (0)
115 117
116#ifdef EINA_SHARE_USAGE 118#ifdef EINA_STRINGSHARE_USAGE
117typedef struct _Eina_Share_Common_Population Eina_Share_Common_Population; 119typedef struct _Eina_Share_Common_Population Eina_Share_Common_Population;
120struct _Eina_Share_Common_Population
121{
122 int count;
123 int max;
124};
118#endif 125#endif
119 126
120typedef struct _Eina_Share_Common Eina_Share_Common; 127typedef struct _Eina_Share_Common Eina_Share_Common;
@@ -125,8 +132,9 @@ struct _Eina_Share
125{ 132{
126 Eina_Share_Common *share; 133 Eina_Share_Common *share;
127 Eina_Magic node_magic; 134 Eina_Magic node_magic;
128#ifdef EINA_SHARE_COMMON_USAGE 135#ifdef EINA_STRINGSHARE_USAGE
129 Eina_Share_Common_Population population; 136 Eina_Share_Common_Population population;
137 Eina_Share_Common_Population population_group[4];
130 int max_node_population; 138 int max_node_population;
131#endif 139#endif
132}; 140};
@@ -156,7 +164,7 @@ struct _Eina_Share_Common_Head
156 164
157 int hash; 165 int hash;
158 166
159#ifdef EINA_SHARE_COMMON_USAGE 167#ifdef EINA_STRINGSHARE_USAGE
160 int population; 168 int population;
161#endif 169#endif
162 170
@@ -168,22 +176,7 @@ Eina_Bool _share_common_threads_activated = EINA_FALSE;
168 176
169static Eina_Lock _mutex_big; 177static Eina_Lock _mutex_big;
170 178
171#ifdef EINA_SHARE_COMMON_USAGE 179#ifdef EINA_STRINGSHARE_USAGE
172struct _Eina_Share_Common_Population
173{
174 int count;
175 int max;
176};
177
178static Eina_Share_Common_Population population = { 0, 0 };
179
180static Eina_Share_Common_Population population_group[4] =
181{
182 { 0, 0 },
183 { 0, 0 },
184 { 0, 0 },
185 { 0, 0 }
186};
187 180
188static void 181static void
189_eina_share_common_population_init(Eina_Share *share) 182_eina_share_common_population_init(Eina_Share *share)
@@ -277,7 +270,7 @@ eina_share_common_population_del(Eina_Share *share, int slen)
277} 270}
278 271
279static void 272static void
280_eina_share_common_population_head_init(Eina_Share *share, 273_eina_share_common_population_head_init(EINA_UNUSED Eina_Share *share,
281 Eina_Share_Common_Head *head) 274 Eina_Share_Common_Head *head)
282{ 275{
283 head->population = 1; 276 head->population = 1;
@@ -293,13 +286,13 @@ _eina_share_common_population_head_add(Eina_Share *share,
293} 286}
294 287
295static void 288static void
296_eina_share_common_population_head_del(Eina_Share *share, 289_eina_share_common_population_head_del(EINA_UNUSED Eina_Share *share,
297 Eina_Share_Common_Head *head) 290 Eina_Share_Common_Head *head)
298{ 291{
299 head->population--; 292 head->population--;
300} 293}
301 294
302#else /* EINA_SHARE_COMMON_USAGE undefined */ 295#else /* EINA_STRINGSHARE_USAGE undefined */
303 296
304static void _eina_share_common_population_init(EINA_UNUSED Eina_Share *share) { 297static void _eina_share_common_population_init(EINA_UNUSED Eina_Share *share) {
305} 298}
@@ -338,7 +331,7 @@ _eina_share_common_cmp(const Eina_Share_Common_Head *ed,
338{ 331{
339 EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(ed, , 0); 332 EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(ed, , 0);
340 333
341 return ed->hash - *hash; 334 return EINA_SHARE_COMMON_NODE_HASH(ed->hash) - *hash;
342} 335}
343 336
344static Eina_Rbtree_Direction 337static Eina_Rbtree_Direction
@@ -349,7 +342,7 @@ _eina_share_common_node(const Eina_Share_Common_Head *left,
349 EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(left, , 0); 342 EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(left, , 0);
350 EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(right, , 0); 343 EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(right, , 0);
351 344
352 if (left->hash - right->hash < 0) 345 if (EINA_SHARE_COMMON_NODE_HASH(left->hash) - EINA_SHARE_COMMON_NODE_HASH(right->hash) < 0)
353 return EINA_RBTREE_LEFT; 346 return EINA_RBTREE_LEFT;
354 347
355 return EINA_RBTREE_RIGHT; 348 return EINA_RBTREE_RIGHT;
@@ -473,10 +466,13 @@ _eina_share_common_head_find(Eina_Share_Common_Head *head,
473 for (; node; prev = node, node = node->next) 466 for (; node; prev = node, node = node->next)
474 if (_eina_share_common_node_eq(node, str, slen)) 467 if (_eina_share_common_node_eq(node, str, slen))
475 { 468 {
476 /* promote node, make hot items be at the beginning */ 469 /* promote node except builtin_node, make hot items be at the beginning */
477 prev->next = node->next; 470 if (node->next)
478 node->next = head->head; 471 {
479 head->head = node; 472 prev->next = node->next;
473 node->next = head->head;
474 head->head = node;
475 }
480 return node; 476 return node;
481 } 477 }
482 478
@@ -515,6 +511,20 @@ _eina_share_common_find_hash(Eina_Share_Common_Head *bucket, int hash)
515 EINA_RBTREE_CMP_KEY_CB(_eina_share_common_cmp), NULL); 511 EINA_RBTREE_CMP_KEY_CB(_eina_share_common_cmp), NULL);
516} 512}
517 513
514static Eina_Share_Common_Head *
515_eina_share_common_head_from_node(Eina_Share_Common_Node *node)
516{
517 Eina_Share_Common_Head *head;
518 const size_t offset = offsetof(Eina_Share_Common_Head, builtin_node);
519
520 while (node->next)
521 node = node->next;
522 head = (Eina_Share_Common_Head *)((char*)node - offset);
523 EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(head, , 0);
524
525 return head;
526}
527
518static Eina_Share_Common_Node * 528static Eina_Share_Common_Node *
519_eina_share_common_node_alloc(unsigned int slen, unsigned int null_size) 529_eina_share_common_node_alloc(unsigned int slen, unsigned int null_size)
520{ 530{
@@ -716,7 +726,7 @@ eina_share_common_add_length(Eina_Share *share,
716{ 726{
717 Eina_Share_Common_Head **p_bucket, *ed; 727 Eina_Share_Common_Head **p_bucket, *ed;
718 Eina_Share_Common_Node *el; 728 Eina_Share_Common_Node *el;
719 int hash_num, hash; 729 int hash;
720 730
721 if (!str) 731 if (!str)
722 return NULL; 732 return NULL;
@@ -727,13 +737,11 @@ eina_share_common_add_length(Eina_Share *share,
727 return NULL; 737 return NULL;
728 738
729 hash = eina_hash_superfast(str, slen); 739 hash = eina_hash_superfast(str, slen);
730 hash_num = hash & 0xFF;
731 hash = (hash >> 8) & EINA_SHARE_COMMON_MASK;
732 740
733 eina_lock_take(&_mutex_big); 741 eina_lock_take(&_mutex_big);
734 p_bucket = share->share->buckets + hash_num; 742 p_bucket = share->share->buckets + EINA_SHARE_COMMON_BUCKET_IDX(hash);
735 743
736 ed = _eina_share_common_find_hash(*p_bucket, hash); 744 ed = _eina_share_common_find_hash(*p_bucket, EINA_SHARE_COMMON_NODE_HASH(hash));
737 if (!ed) 745 if (!ed)
738 { 746 {
739 const char *s = _eina_share_common_add_head(share, 747 const char *s = _eina_share_common_add_head(share,
@@ -808,7 +816,6 @@ eina_share_common_del(Eina_Share *share, const char *str)
808 Eina_Share_Common_Head *ed; 816 Eina_Share_Common_Head *ed;
809 Eina_Share_Common_Head **p_bucket; 817 Eina_Share_Common_Head **p_bucket;
810 Eina_Share_Common_Node *node; 818 Eina_Share_Common_Node *node;
811 int hash_num, hash;
812 819
813 if (!str) 820 if (!str)
814 return EINA_TRUE; 821 return EINA_TRUE;
@@ -830,25 +837,24 @@ eina_share_common_del(Eina_Share *share, const char *str)
830 837
831 node->references = 0; 838 node->references = 0;
832 839
833 hash = eina_hash_superfast(str, slen); 840 ed = _eina_share_common_head_from_node(node);
834 hash_num = hash & 0xFF;
835 hash = (hash >> 8) & EINA_SHARE_COMMON_MASK;
836
837 p_bucket = share->share->buckets + hash_num;
838 ed = _eina_share_common_find_hash(*p_bucket, hash);
839 if (!ed) 841 if (!ed)
840 goto on_error; 842 goto on_error;
841 843
842 EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(ed, eina_lock_release(&_mutex_big), EINA_FALSE); 844 EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(ed, eina_lock_release(&_mutex_big), EINA_FALSE);
843 845
844 if (!_eina_share_common_head_remove_node(ed, node))
845 goto on_error;
846
847 if (node != &ed->builtin_node) 846 if (node != &ed->builtin_node)
848 MAGIC_FREE(node); 847 {
848 if (!_eina_share_common_head_remove_node(ed, node))
849 goto on_error;
850 MAGIC_FREE(node);
851 }
849 852
850 if (!ed->head) 853 if (!ed->head || ed->head->references == 0)
851 _eina_share_common_del_head(p_bucket, ed); 854 {
855 p_bucket = share->share->buckets + EINA_SHARE_COMMON_BUCKET_IDX(ed->hash);
856 _eina_share_common_del_head(p_bucket, ed);
857 }
852 else 858 else
853 _eina_share_common_population_head_del(share, ed); 859 _eina_share_common_population_head_del(share, ed);
854 860
@@ -911,7 +917,7 @@ eina_share_common_dump(Eina_Share *share, void (*additional_dump)(
911 if (additional_dump) 917 if (additional_dump)
912 additional_dump(&di); 918 additional_dump(&di);
913 919
914#ifdef EINA_SHARE_COMMON_USAGE 920#ifdef EINA_STRINGSHARE_USAGE
915 /* One character strings are not counted in the hash. */ 921 /* One character strings are not counted in the hash. */
916 di.saved += share->population_group[0].count * sizeof(char); 922 di.saved += share->population_group[0].count * sizeof(char);
917 di.saved += share->population_group[1].count * sizeof(char) * 2; 923 di.saved += share->population_group[1].count * sizeof(char) * 2;
@@ -922,9 +928,10 @@ eina_share_common_dump(Eina_Share *share, void (*additional_dump)(
922 printf("DDD: unique: %d, duplicates: %d (%3.0f%%)\n", 928 printf("DDD: unique: %d, duplicates: %d (%3.0f%%)\n",
923 di.unique, di.dups, di.unique ? (di.dups * 100.0 / di.unique) : 0.0); 929 di.unique, di.dups, di.unique ? (di.dups * 100.0 / di.unique) : 0.0);
924 930
925#ifdef EINA_SHARE_COMMON_USAGE 931#ifdef EINA_STRINGSHARE_USAGE
926 printf("DDD: Allocated strings: %i\n", share->population.count); 932 printf("DDD: Allocated strings: %i\n", share->population.count);
927 printf("DDD: Max allocated strings: %i\n", share->population.max); 933 printf("DDD: Max allocated strings: %i\n", share->population.max);
934 printf("DDD: Max shared strings per node : %i\n", share->max_node_population);
928 935
929 for (i = 0; 936 for (i = 0;
930 i < sizeof (share->population_group) / 937 i < sizeof (share->population_group) /
diff --git a/src/lib/eina/eina_stringshare.c b/src/lib/eina/eina_stringshare.c
index 2acb98c..ceae4f3 100644
--- a/src/lib/eina/eina_stringshare.c
+++ b/src/lib/eina/eina_stringshare.c
@@ -578,13 +578,18 @@ eina_stringshare_del(Eina_Stringshare *str)
578 slen = 4; /* handled later */ 578 slen = 4; /* handled later */
579 579
580 if (slen < 2) 580 if (slen < 2)
581 return; 581 {
582 eina_share_common_population_del(stringshare_share, slen);
583
584 return;
585 }
582 else if (slen < 4) 586 else if (slen < 4)
583 { 587 {
584 eina_share_common_population_del(stringshare_share, slen); 588 eina_share_common_population_del(stringshare_share, slen);
585 eina_lock_take(&_mutex_small); 589 eina_lock_take(&_mutex_small);
586 _eina_stringshare_small_del(str, slen); 590 _eina_stringshare_small_del(str, slen);
587 eina_lock_release(&_mutex_small); 591 eina_lock_release(&_mutex_small);
592
588 return; 593 return;
589 } 594 }
590 595
@@ -598,16 +603,26 @@ eina_stringshare_add_length(const char *str, unsigned int slen)
598 if (!str) 603 if (!str)
599 return NULL; 604 return NULL;
600 else if (slen == 0) 605 else if (slen == 0)
601 return ""; 606 {
607 eina_share_common_population_add(stringshare_share, slen);
608
609 return "";
610 }
602 else if (slen == 1) 611 else if (slen == 1)
603 return (Eina_Stringshare *) _eina_stringshare_single + ((*str) << 1); 612 {
613 eina_share_common_population_add(stringshare_share, slen);
614
615 return (Eina_Stringshare *) _eina_stringshare_single + ((*str) << 1);
616 }
604 else if (slen < 4) 617 else if (slen < 4)
605 { 618 {
606 const char *s; 619 const char *s;
607 620
621 eina_share_common_population_add(stringshare_share, slen);
608 eina_lock_take(&_mutex_small); 622 eina_lock_take(&_mutex_small);
609 s = _eina_stringshare_small_add(str, slen); 623 s = _eina_stringshare_small_add(str, slen);
610 eina_lock_release(&_mutex_small); 624 eina_lock_release(&_mutex_small);
625
611 return s; 626 return s;
612 } 627 }
613 628
@@ -712,7 +727,7 @@ eina_stringshare_ref(Eina_Stringshare *str)
712 int slen; 727 int slen;
713 728
714 if (!str) 729 if (!str)
715 return eina_share_common_ref(stringshare_share, str); 730 return NULL;
716 731
717 /* special cases */ 732 /* special cases */
718 if (str[0] == '\0') 733 if (str[0] == '\0')
@@ -735,8 +750,8 @@ eina_stringshare_ref(Eina_Stringshare *str)
735 else if (slen < 4) 750 else if (slen < 4)
736 { 751 {
737 const char *s; 752 const char *s;
738 eina_share_common_population_add(stringshare_share, slen);
739 753
754 eina_share_common_population_add(stringshare_share, slen);
740 eina_lock_take(&_mutex_small); 755 eina_lock_take(&_mutex_small);
741 s = _eina_stringshare_small_add(str, slen); 756 s = _eina_stringshare_small_add(str, slen);
742 eina_lock_release(&_mutex_small); 757 eina_lock_release(&_mutex_small);