From d8cb6f5e2eff22d4cb232ffdb10bd8b734726508 Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Thu, 2 Jun 2011 21:53:16 +0000 Subject: speedup lookups by avoiding heap allocations New_Prefix2 takes a second argument which allows us to use a static or stack variable to avoid hitting the heap. This results in speedups for places where we previously allocated and freed a prefix: --------------------------- 8< ------------------------ require "rpatricia" require "benchmark" nr = 1000000 addr = "127.1.1.1" p = Patricia.new p.add "127.0.0.0/8" res = Benchmark.measure do nr.times { p.include?(addr) } end p res --------------------------- 8< ------------------------ user system total real before 0.470000 0.000000 0.470000 ( 0.467902) after 0.330000 0.000000 0.330000 ( 0.328538) --- ext/rpatricia/patricia.c | 9 ++++---- ext/rpatricia/patricia.h | 2 +- ext/rpatricia/rpatricia.c | 53 +++++++++++++++++++---------------------------- 3 files changed, 26 insertions(+), 38 deletions(-) diff --git a/ext/rpatricia/patricia.c b/ext/rpatricia/patricia.c index 44cc01c..9913a3f 100644 --- a/ext/rpatricia/patricia.c +++ b/ext/rpatricia/patricia.c @@ -148,9 +148,8 @@ New_Prefix (int family, void *dest, int bitlen) /* ascii2prefix */ prefix_t * -ascii2prefix(char *string) +ascii2prefix(char *string, prefix_t *prefix) { - prefix_t *prefix; long bitlen; size_t maxbitlen; void *dest; @@ -185,10 +184,10 @@ ascii2prefix(char *string) if (result != 1) return NULL; - return New_Prefix2(family, &addr, bitlen, NULL); + return New_Prefix2(family, &addr, bitlen, prefix); } -prefix_t * +static prefix_t * Ref_Prefix (prefix_t * prefix) { if (prefix == NULL) @@ -201,7 +200,7 @@ Ref_Prefix (prefix_t * prefix) return (prefix); } -void +static void Deref_Prefix (prefix_t * prefix) { if (prefix == NULL) diff --git a/ext/rpatricia/patricia.h b/ext/rpatricia/patricia.h index f4abffd..4bde733 100644 --- a/ext/rpatricia/patricia.h +++ b/ext/rpatricia/patricia.h @@ -86,7 +86,7 @@ void patricia_process (patricia_tree_t *patricia, void_fn_t func); /* { from demo.c */ prefix_t * -ascii2prefix (char *string); +ascii2prefix (char *string, prefix_t *prefix); /* } */ diff --git a/ext/rpatricia/rpatricia.c b/ext/rpatricia/rpatricia.c index 4132c32..066f82e 100644 --- a/ext/rpatricia/rpatricia.c +++ b/ext/rpatricia/rpatricia.c @@ -43,24 +43,18 @@ wrap_node(patricia_node_t *orig) return Data_Wrap_Struct(cNode, p_node_mark, -1, node); } -static prefix_t * -my_ascii2prefix(patricia_tree_t *tree, VALUE str) +static void +my_ascii2prefix(patricia_tree_t *tree, VALUE str, prefix_t *prefix) { char *cstr = StringValuePtr(str); - prefix_t *prefix = ascii2prefix(cstr); + prefix_t *ok = ascii2prefix(cstr, prefix); - if (!prefix) + if (!ok) rb_raise(rb_eArgError, "invalid prefix: %s", cstr); - if (prefix->bitlen > tree->maxbits) { - unsigned bitlen = prefix->bitlen; - - Deref_Prefix(prefix); + if (prefix->bitlen > tree->maxbits) rb_raise(rb_eArgError, "prefix length (%u) larger than maxbits (%u)", - bitlen, tree->maxbits); - } - - return prefix; + prefix->bitlen, tree->maxbits); } static VALUE @@ -69,15 +63,14 @@ p_add (int argc, VALUE *argv, VALUE self) VALUE user_data; patricia_tree_t *tree; patricia_node_t *node; - prefix_t *prefix; + prefix_t prefix; if (argc > 2 || argc < 1) return Qnil; Data_Get_Struct(self, patricia_tree_t, tree); - prefix = my_ascii2prefix(tree, argv[0]); - node = patricia_lookup(tree, prefix); - Deref_Prefix(prefix); + my_ascii2prefix(tree, argv[0], &prefix); + node = patricia_lookup(tree, &prefix); if (argc == 2) { user_data = argv[1]; @@ -99,12 +92,11 @@ p_remove (VALUE self, VALUE r_key) { patricia_tree_t *tree; patricia_node_t *node; - prefix_t *prefix; + prefix_t prefix; Data_Get_Struct(self, patricia_tree_t, tree); - prefix = my_ascii2prefix(tree, r_key); - node = patricia_search_exact(tree, prefix); - Deref_Prefix (prefix); + my_ascii2prefix(tree, r_key, &prefix); + node = patricia_search_exact(tree, &prefix); if (node) { patricia_remove (tree, node); @@ -119,12 +111,11 @@ p_match (VALUE self, VALUE r_key) { patricia_tree_t *tree; patricia_node_t *node; - prefix_t *prefix; + prefix_t prefix; Data_Get_Struct(self, patricia_tree_t, tree); - prefix = my_ascii2prefix(tree, r_key); - node = patricia_search_best(tree, prefix); - Deref_Prefix (prefix); + my_ascii2prefix(tree, r_key, &prefix); + node = patricia_search_best(tree, &prefix); return node ? wrap_node(node) : Qnil; } @@ -134,12 +125,11 @@ p_include (VALUE self, VALUE r_key) { patricia_tree_t *tree; patricia_node_t *node; - prefix_t *prefix; + prefix_t prefix; Data_Get_Struct(self, patricia_tree_t, tree); - prefix = my_ascii2prefix(tree, r_key); - node = patricia_search_best(tree, prefix); - Deref_Prefix (prefix); + my_ascii2prefix(tree, r_key, &prefix); + node = patricia_search_best(tree, &prefix); return node ? Qtrue : Qfalse; } @@ -149,12 +139,11 @@ p_match_exact (VALUE self, VALUE r_key) { patricia_tree_t *tree; patricia_node_t *node; - prefix_t *prefix; + prefix_t prefix; Data_Get_Struct(self, patricia_tree_t, tree); - prefix = my_ascii2prefix(tree, r_key); - node = patricia_search_exact(tree, prefix); - Deref_Prefix (prefix); + my_ascii2prefix(tree, r_key, &prefix); + node = patricia_search_exact(tree, &prefix); return node ? wrap_node(node) : Qnil; } -- cgit v1.2.3-24-ge0c7