the patches, the bench code and the git based script I used to collect them are attached charts too
here are the numbers,
they are not very impressive like that,
the optimized path is not easily triggered,
but when it does, it worth it.
not easy to speed up such a good work !
add del full
==> head/run-release-0 <==
10000 2 1 4 [ms]
20000 5 3 8 [ms]
30000 6 5 11 [ms]
40000 10 7 17 [ms]
50000 12 9 22 [ms]
60000 17 12 29 [ms]
70000 19 15 35 [ms]
80000 25 19 44 [ms]
90000 27 22 50 [ms]
100000 34 26 60 [ms]
==> 0001/run-release-0 <==
10000 2 1 4 [ms]
20000 4 3 8 [ms]
30000 6 5 11 [ms]
40000 10 7 17 [ms]
50000 12 9 22 [ms]
60000 16 12 28 [ms]
70000 19 15 34 [ms]
80000 25 19 44 [ms]
90000 27 22 50 [ms]
100000 34 26 60 [ms]
==> 0002/run-release-0 <==
10000 2 1 3 [ms]
20000 4 2 7 [ms]
30000 6 3 10 [ms]
40000 9 5 15 [ms]
50000 12 7 20 [ms]
60000 16 9 26 [ms]
70000 18 12 31 [ms]
80000 24 15 40 [ms]
90000 27 18 46 [ms]
100000 34 21 56 [ms]
==> 0003/run-release-0 <==
10000 2 1 3 [ms]
20000 5 2 7 [ms]
30000 6 3 10 [ms]
40000 9 4 14 [ms]
50000 12 6 19 [ms]
60000 16 8 25 [ms]
70000 18 11 30 [ms]
80000 24 14 38 [ms]
90000 27 17 44 [ms]
100000 34 20 54 [ms]
Jérémy Zurcher
build_patches.sh
Description: Bourne shell script
#include <stdio.h>
#include <time.h>
#include <Eina.h>
#include <stdint.h>
static const char **shares;
static int64_t time_diff(struct timespec *t0, struct timespec *t1)
{
return ((t1->tv_sec * 1000000000) + t1->tv_nsec) - ((t0->tv_sec * 1000000000) + t0->tv_nsec);
}
static void add(int n)
{
unsigned int i;
const char *none;
const char **walker;
char build[64] = "string_";
walker = shares;
for (i = 0; i < n; ++i, ++walker)
{
eina_convert_xtoa(i, build + 7);
*walker = eina_stringshare_add(build);
}
/* ref */
/* for (i = 0; i < n; ++i) */
/* { */
/* eina_convert_xtoa(i, build + 7); */
/* none = eina_stringshare_add(build); */
/* } */
}
static void del(int n)
{
unsigned int i;
unsigned int l;
const char **walker;
/* unref */
walker = shares;
/* for (i = 0; i < n; ++i, ++walker) */
/* { */
/* eina_stringshare_del(*walker); */
/* } */
l = n/4;
/* | | |->| | */
walker = &shares[n/2];
for (i = 0; i < l; ++i, ++walker)
{
eina_stringshare_del(*walker);
}
/* | | | |<-| */
walker = &shares[n-1];
for (i = 0; i < l; ++i, --walker)
{
eina_stringshare_del(*walker);
}
/* | |->| | | */
walker = &shares[n/4];
for (i = 0; i < l; ++i, ++walker)
{
eina_stringshare_del(*walker);
}
/* |<-| | | | */
walker = &shares[n/4-1];
for (i = 0; i < l; ++i, --walker)
{
eina_stringshare_del(*walker);
}
}
static void run(int n)
{
uint64_t dt0, dt1, dt2;
struct timespec t0, t1, t2;
eina_init();
shares = calloc(n+1,sizeof(char*));
shares[n]=0;
clock_gettime(CLOCK_MONOTONIC, &t0);
add(n);
clock_gettime(CLOCK_MONOTONIC, &t1);
del(n);
/* eina_stringshare_dump(); */
clock_gettime(CLOCK_MONOTONIC, &t2);
eina_shutdown();
free(shares);
dt0 = time_diff(&t0,&t1);
dt1 = time_diff(&t1,&t2);
dt2 = time_diff(&t0,&t2);
fprintf(stdout,"%d\t%4d\t%4d\t%4d [ms]\n",n,(int)(dt0/1000000),(int)(dt1/1000000),(int)(dt2/1000000));
}
int main(int argc, char *argv[])
{
int i;
for (i = 10000; i<=100000; i += 10000)
run(i);
return 0;
}
>From 2c97a247de042db11251a7d4638041d49b10319c Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jer...@asynk.ch>
Date: Fri, 14 Dec 2012 16:58:26 +0100
Subject: [PATCH 1/4] eina_stringshare: fix common population accounting
use EINA_STRINGSHARE_USAGE (setable through configure),
instead of EINA_SHARE_USAGE and EINA_SHARE_COMMON_USAGE
---
---
efl/src/lib/eina/eina_share_common.c | 40 +++++++++++++++---------------------
efl/src/lib/eina/eina_stringshare.c | 25 +++++++++++++++++-----
2 files changed, 36 insertions(+), 29 deletions(-)
diff --git a/efl/src/lib/eina/eina_share_common.c
b/efl/src/lib/eina/eina_share_common.c
index 29c9f47..df3246d 100644
--- a/efl/src/lib/eina/eina_share_common.c
+++ b/efl/src/lib/eina/eina_share_common.c
@@ -113,8 +113,13 @@ static int _eina_share_common_count = 0;
} \
} while (0)
-#ifdef EINA_SHARE_USAGE
+#ifdef EINA_STRINGSHARE_USAGE
typedef struct _Eina_Share_Common_Population Eina_Share_Common_Population;
+struct _Eina_Share_Common_Population
+{
+ int count;
+ int max;
+};
#endif
typedef struct _Eina_Share_Common Eina_Share_Common;
@@ -125,8 +130,9 @@ struct _Eina_Share
{
Eina_Share_Common *share;
Eina_Magic node_magic;
-#ifdef EINA_SHARE_COMMON_USAGE
+#ifdef EINA_STRINGSHARE_USAGE
Eina_Share_Common_Population population;
+ Eina_Share_Common_Population population_group[4];
int max_node_population;
#endif
};
@@ -156,7 +162,7 @@ struct _Eina_Share_Common_Head
int hash;
-#ifdef EINA_SHARE_COMMON_USAGE
+#ifdef EINA_STRINGSHARE_USAGE
int population;
#endif
@@ -168,22 +174,7 @@ Eina_Bool _share_common_threads_activated = EINA_FALSE;
static Eina_Lock _mutex_big;
-#ifdef EINA_SHARE_COMMON_USAGE
-struct _Eina_Share_Common_Population
-{
- int count;
- int max;
-};
-
-static Eina_Share_Common_Population population = { 0, 0 };
-
-static Eina_Share_Common_Population population_group[4] =
-{
- { 0, 0 },
- { 0, 0 },
- { 0, 0 },
- { 0, 0 }
-};
+#ifdef EINA_STRINGSHARE_USAGE
static void
_eina_share_common_population_init(Eina_Share *share)
@@ -277,7 +268,7 @@ eina_share_common_population_del(Eina_Share *share, int
slen)
}
static void
-_eina_share_common_population_head_init(Eina_Share *share,
+_eina_share_common_population_head_init(EINA_UNUSED Eina_Share *share,
Eina_Share_Common_Head *head)
{
head->population = 1;
@@ -293,13 +284,13 @@ _eina_share_common_population_head_add(Eina_Share *share,
}
static void
-_eina_share_common_population_head_del(Eina_Share *share,
+_eina_share_common_population_head_del(EINA_UNUSED Eina_Share *share,
Eina_Share_Common_Head *head)
{
head->population--;
}
-#else /* EINA_SHARE_COMMON_USAGE undefined */
+#else /* EINA_STRINGSHARE_USAGE undefined */
static void _eina_share_common_population_init(EINA_UNUSED Eina_Share *share) {
}
@@ -911,7 +902,7 @@ eina_share_common_dump(Eina_Share *share, void
(*additional_dump)(
if (additional_dump)
additional_dump(&di);
-#ifdef EINA_SHARE_COMMON_USAGE
+#ifdef EINA_STRINGSHARE_USAGE
/* One character strings are not counted in the hash. */
di.saved += share->population_group[0].count * sizeof(char);
di.saved += share->population_group[1].count * sizeof(char) * 2;
@@ -922,9 +913,10 @@ eina_share_common_dump(Eina_Share *share, void
(*additional_dump)(
printf("DDD: unique: %d, duplicates: %d (%3.0f%%)\n",
di.unique, di.dups, di.unique ? (di.dups * 100.0 / di.unique) : 0.0);
-#ifdef EINA_SHARE_COMMON_USAGE
+#ifdef EINA_STRINGSHARE_USAGE
printf("DDD: Allocated strings: %i\n", share->population.count);
printf("DDD: Max allocated strings: %i\n", share->population.max);
+ printf("DDD: Max shared strings per node : %i\n",
share->max_node_population);
for (i = 0;
i < sizeof (share->population_group) /
diff --git a/efl/src/lib/eina/eina_stringshare.c
b/efl/src/lib/eina/eina_stringshare.c
index 2acb98c..ceae4f3 100644
--- a/efl/src/lib/eina/eina_stringshare.c
+++ b/efl/src/lib/eina/eina_stringshare.c
@@ -578,13 +578,18 @@ eina_stringshare_del(Eina_Stringshare *str)
slen = 4; /* handled later */
if (slen < 2)
- return;
+ {
+ eina_share_common_population_del(stringshare_share, slen);
+
+ return;
+ }
else if (slen < 4)
{
eina_share_common_population_del(stringshare_share, slen);
eina_lock_take(&_mutex_small);
_eina_stringshare_small_del(str, slen);
eina_lock_release(&_mutex_small);
+
return;
}
@@ -598,16 +603,26 @@ eina_stringshare_add_length(const char *str, unsigned int
slen)
if (!str)
return NULL;
else if (slen == 0)
- return "";
+ {
+ eina_share_common_population_add(stringshare_share, slen);
+
+ return "";
+ }
else if (slen == 1)
- return (Eina_Stringshare *) _eina_stringshare_single + ((*str) << 1);
+ {
+ eina_share_common_population_add(stringshare_share, slen);
+
+ return (Eina_Stringshare *) _eina_stringshare_single + ((*str) << 1);
+ }
else if (slen < 4)
{
const char *s;
+ eina_share_common_population_add(stringshare_share, slen);
eina_lock_take(&_mutex_small);
s = _eina_stringshare_small_add(str, slen);
eina_lock_release(&_mutex_small);
+
return s;
}
@@ -712,7 +727,7 @@ eina_stringshare_ref(Eina_Stringshare *str)
int slen;
if (!str)
- return eina_share_common_ref(stringshare_share, str);
+ return NULL;
/* special cases */
if (str[0] == '\0')
@@ -735,8 +750,8 @@ eina_stringshare_ref(Eina_Stringshare *str)
else if (slen < 4)
{
const char *s;
- eina_share_common_population_add(stringshare_share, slen);
+ eina_share_common_population_add(stringshare_share, slen);
eina_lock_take(&_mutex_small);
s = _eina_stringshare_small_add(str, slen);
eina_lock_release(&_mutex_small);
--
1.8.1
>From bf19635771a3f3ccc849f765c8c93d05c8a645bd Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jer...@asynk.ch>
Date: Thu, 29 Nov 2012 09:46:39 +0100
Subject: [PATCH 2/4] eina_share_common_del speed up
builtin node is never unlinked even if empty, always is the last of the
queue (never promoted), 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.
---
efl/src/lib/eina/eina_share_common.c | 50 ++++++++++++++++++++++++------------
1 file changed, 34 insertions(+), 16 deletions(-)
diff --git a/efl/src/lib/eina/eina_share_common.c
b/efl/src/lib/eina/eina_share_common.c
index df3246d..2f6f485 100644
--- a/efl/src/lib/eina/eina_share_common.c
+++ b/efl/src/lib/eina/eina_share_common.c
@@ -464,10 +464,13 @@ _eina_share_common_head_find(Eina_Share_Common_Head *head,
for (; node; prev = node, node = node->next)
if (_eina_share_common_node_eq(node, str, slen))
{
- /* promote node, make hot items be at the beginning */
- prev->next = node->next;
- node->next = head->head;
- head->head = node;
+ /* promote node except builtin_node, make hot items be at the
beginning */
+ if (node->next)
+ {
+ prev->next = node->next;
+ node->next = head->head;
+ head->head = node;
+ }
return node;
}
@@ -506,6 +509,20 @@ _eina_share_common_find_hash(Eina_Share_Common_Head
*bucket, int hash)
EINA_RBTREE_CMP_KEY_CB(_eina_share_common_cmp), NULL);
}
+static Eina_Share_Common_Head *
+_eina_share_common_head_from_node(Eina_Share_Common_Node *node)
+{
+ Eina_Share_Common_Head *head;
+ const size_t offset = offsetof(Eina_Share_Common_Head, builtin_node);
+
+ while (node->next)
+ node = node->next;
+ head = (Eina_Share_Common_Head *)((char*)node - offset);
+ EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(head, , 0);
+
+ return head;
+}
+
static Eina_Share_Common_Node *
_eina_share_common_node_alloc(unsigned int slen, unsigned int null_size)
{
@@ -821,25 +838,26 @@ eina_share_common_del(Eina_Share *share, const char *str)
node->references = 0;
- hash = eina_hash_superfast(str, slen);
- hash_num = hash & 0xFF;
- hash = (hash >> 8) & EINA_SHARE_COMMON_MASK;
-
- p_bucket = share->share->buckets + hash_num;
- ed = _eina_share_common_find_hash(*p_bucket, hash);
+ ed = _eina_share_common_head_from_node(node);
if (!ed)
goto on_error;
EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(ed, eina_lock_release(&_mutex_big),
EINA_FALSE);
- if (!_eina_share_common_head_remove_node(ed, node))
- goto on_error;
-
if (node != &ed->builtin_node)
- MAGIC_FREE(node);
+ {
+ if (!_eina_share_common_head_remove_node(ed, node))
+ goto on_error;
+ MAGIC_FREE(node);
+ }
- if (!ed->head)
- _eina_share_common_del_head(p_bucket, ed);
+ if (!ed->head || ed->head->references == 0)
+ {
+ hash = eina_hash_superfast(str, slen);
+ hash_num = hash & 0xFF;
+ p_bucket = share->share->buckets + hash_num;
+ _eina_share_common_del_head(p_bucket, ed);
+ }
else
_eina_share_common_population_head_del(share, ed);
--
1.8.1
>From edd87aa31f06bcc07469f38705cf890d9055c07e Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jer...@asynk.ch>
Date: Thu, 29 Nov 2012 09:47:21 +0100
Subject: [PATCH 3/4] eina_share_common_del speed up
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.
---
efl/src/lib/eina/eina_share_common.c | 19 ++++++++-----------
1 file changed, 8 insertions(+), 11 deletions(-)
diff --git a/efl/src/lib/eina/eina_share_common.c
b/efl/src/lib/eina/eina_share_common.c
index 2f6f485..0dbf37d 100644
--- a/efl/src/lib/eina/eina_share_common.c
+++ b/efl/src/lib/eina/eina_share_common.c
@@ -88,6 +88,8 @@
#define EINA_SHARE_COMMON_BUCKETS 256
#define EINA_SHARE_COMMON_MASK 0xFF
+#define EINA_SHARE_COMMON_BUCKET_IDX(h) ((h >> 8) & EINA_SHARE_COMMON_MASK)
+#define EINA_SHARE_COMMON_NODE_HASH(h) (h & EINA_SHARE_COMMON_MASK)
static const char EINA_MAGIC_SHARE_STR[] = "Eina Share";
static const char EINA_MAGIC_SHARE_HEAD_STR[] = "Eina Share Head";
@@ -329,7 +331,7 @@ _eina_share_common_cmp(const Eina_Share_Common_Head *ed,
{
EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(ed, , 0);
- return ed->hash - *hash;
+ return EINA_SHARE_COMMON_NODE_HASH(ed->hash) - *hash;
}
static Eina_Rbtree_Direction
@@ -340,7 +342,7 @@ _eina_share_common_node(const Eina_Share_Common_Head *left,
EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(left, , 0);
EINA_MAGIC_CHECK_SHARE_COMMON_HEAD(right, , 0);
- if (left->hash - right->hash < 0)
+ if (EINA_SHARE_COMMON_NODE_HASH(left->hash) -
EINA_SHARE_COMMON_NODE_HASH(right->hash) < 0)
return EINA_RBTREE_LEFT;
return EINA_RBTREE_RIGHT;
@@ -724,7 +726,7 @@ eina_share_common_add_length(Eina_Share *share,
{
Eina_Share_Common_Head **p_bucket, *ed;
Eina_Share_Common_Node *el;
- int hash_num, hash;
+ int hash;
if (!str)
return NULL;
@@ -735,13 +737,11 @@ eina_share_common_add_length(Eina_Share *share,
return NULL;
hash = eina_hash_superfast(str, slen);
- hash_num = hash & 0xFF;
- hash = (hash >> 8) & EINA_SHARE_COMMON_MASK;
eina_lock_take(&_mutex_big);
- p_bucket = share->share->buckets + hash_num;
+ p_bucket = share->share->buckets + EINA_SHARE_COMMON_BUCKET_IDX(hash);
- ed = _eina_share_common_find_hash(*p_bucket, hash);
+ ed = _eina_share_common_find_hash(*p_bucket,
EINA_SHARE_COMMON_NODE_HASH(hash));
if (!ed)
{
const char *s = _eina_share_common_add_head(share,
@@ -816,7 +816,6 @@ eina_share_common_del(Eina_Share *share, const char *str)
Eina_Share_Common_Head *ed;
Eina_Share_Common_Head **p_bucket;
Eina_Share_Common_Node *node;
- int hash_num, hash;
if (!str)
return EINA_TRUE;
@@ -853,9 +852,7 @@ eina_share_common_del(Eina_Share *share, const char *str)
if (!ed->head || ed->head->references == 0)
{
- hash = eina_hash_superfast(str, slen);
- hash_num = hash & 0xFF;
- p_bucket = share->share->buckets + hash_num;
+ p_bucket = share->share->buckets +
EINA_SHARE_COMMON_BUCKET_IDX(ed->hash);
_eina_share_common_del_head(p_bucket, ed);
}
else
--
1.8.1
<<attachment: run-release-add-0.png>>
<<attachment: run-release-del-0.png>>
<<attachment: run-release-full-0.png>>
------------------------------------------------------------------------------ Master Visual Studio, SharePoint, SQL, ASP.NET, C# 2012, HTML5, CSS, MVC, Windows 8 Apps, JavaScript and much more. Keep your skills current with LearnDevNow - 3,200 step-by-step video tutorials by Microsoft MVPs and experts. ON SALE this month only -- learn more at: http://p.sf.net/sfu/learnmore_122712
_______________________________________________ enlightenment-devel mailing list enlightenment-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
