Hi,
here are 2 patches to speed up eina_share_common_del with minimal costs on
eina_share_common_add side.
the second might be controversial
0001-eina_share_common_del-speed-up.patch
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.
0002-eina_share_common_del-speed-up.patch
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.
regards
Jérémy
>From b8dbbedd49e8c66ff1fe201706c1e6a805f009f5 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jer...@asynk.ch>
Date: Tue, 20 Nov 2012 22:31:46 +0100
Subject: [PATCH 1/2] 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.
---
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 c68e399..bc9ea4b 100644
--- a/efl/src/lib/eina/eina_share_common.c
+++ b/efl/src/lib/eina/eina_share_common.c
@@ -477,10 +477,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;
}
@@ -519,6 +522,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)
{
@@ -834,25 +851,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.0
>From dbe93a06190383b3e4ba283d6453398bcf7c324a Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jer...@asynk.ch>
Date: Tue, 20 Nov 2012 23:07:16 +0100
Subject: [PATCH 2/2] 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 bc9ea4b..2244df8 100644
--- a/efl/src/lib/eina/eina_share_common.c
+++ b/efl/src/lib/eina/eina_share_common.c
@@ -92,6 +92,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";
@@ -342,7 +344,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
@@ -353,7 +355,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;
@@ -737,7 +739,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;
@@ -748,13 +750,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,
@@ -829,7 +829,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;
@@ -866,9 +865,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.0
------------------------------------------------------------------------------
Monitor your physical, virtual and cloud infrastructure from a single
web console. Get in-depth insight into apps, servers, databases, vmware,
SAP, cloud infrastructure, etc. Download 30-day Free Trial.
Pricing starts from $795 for 25 servers or applications!
http://p.sf.net/sfu/zoho_dev2dev_nov
_______________________________________________
enlightenment-devel mailing list
enlightenment-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
