www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Re: Perfect hashing for string switch

reply bearophile <bearophileHUGS lycos.com> writes:
BCS:
 Have you compared it to a decisition tree or lex style state mechine?

I have now implemented that too, it was not an immediate thing to do (I have removed the versions 2 to 5 to reduce code size on codepad): http://codepad.org/zOmPeE13 The results are good: Timings, ldc, seconds: test1: 4.48 // normal string switch test2: 2.98 // perfect hash test3: 2.09 test4: 2.07 test5: 5.44 // AA. Tango AA opIn_r is bug-slow test6: 1.18 // new result I hope this is enough. I have created that large finite state machine in D with a Python program :-) Bye, bearophile
Jan 27 2010
parent reply Matti Niemenmaa <see_signature for.real.address> writes:
On 2010-01-27 15:17, bearophile wrote:
 BCS:
 Have you compared it to a decisition tree or lex style state mechine?

I have now implemented that too, it was not an immediate thing to do (I have removed the versions 2 to 5 to reduce code size on codepad): http://codepad.org/zOmPeE13 The results are good: Timings, ldc, seconds: test1: 4.48 // normal string switch test2: 2.98 // perfect hash test3: 2.09 test4: 2.07 test5: 5.44 // AA. Tango AA opIn_r is bug-slow test6: 1.18 // new result I hope this is enough. I have created that large finite state machine in D with a Python program :-)

Your test6 is invalid: it reads beyond the bounds of the given array. For example with input "th", it will check whether the third character is 'i'; but the length of the array is only 2, so it shouldn't be doing that. -- E-mail address: matti.niemenmaa+news, domain is iki (DOT) fi
Jan 27 2010
next sibling parent BCS <none anon.com> writes:
Hello Matti,

 On 2010-01-27 15:17, bearophile wrote:
 
 BCS:
 
 Have you compared it to a decisition tree or lex style state
 mechine?
 

(I have removed the versions 2 to 5 to reduce code size on codepad): http://codepad.org/zOmPeE13 The results are good: Timings, ldc, seconds: test1: 4.48 // normal string switch test2: 2.98 // perfect hash test3: 2.09 test4: 2.07 test5: 5.44 // AA. Tango AA opIn_r is bug-slow test6: 1.18 // new result I hope this is enough. I have created that large finite state machine in D with a Python program :-)

For example with input "th", it will check whether the third character is 'i'; but the length of the array is only 2, so it shouldn't be doing that.

A simple fix to that is to make he first transition of the state machine based on the length of the key. that is, 'if' at the top becomes: switch(word.length) { case 13: goto S...: case 12: goto S...: case 11: goto S...: case 10: goto S...: case 9: goto S...: case 8: goto S...: case 7: goto S...: case 6: goto S...: case 5: goto S...: case 4: goto S...: case 3: goto S...: case 2: goto S...: default: goto UNREC; } -- <IXOYE><
Jan 27 2010
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Matti Niemenmaa:
 Your test6 is invalid: it reads beyond the bounds of the given array. 
 For example with input "th", it will check whether the third character 
 is 'i'; but the length of the array is only 2, so it shouldn't be doing 
 that.

Shame on me, I am sorry -.- Thank you. I will try to improve the code later. The good thing is that D2 allows me to implement something to catch that kind of out-of-range pointer errors at run-time (D1 is not good enough here). That code at the bottom is not well tested yet, so it can contain many bugs. And probably it's not const-aware yet (if someone has suggestions to improve it I will appreciate them). In programs a certain percentage of pointers run inside an interval of memory, so something like this can be useful. Do you think this is (once well debugged and improved) useful for Phobos2? Up sides: - this code seems to work and catchs the bug at runtime in the test6() function I've written. Downsides: - currently compiled with D2 the test6() gets slower even when the code is not in debug release. Future D2 compilers will need to reduce to zero or near zero this overhead, so safer pointers can be used more freely. Possible future improvements: use an "interval tree" where necessary to quickly find if the pointer is inside more than one interval. This is probably a quite less common need. Bye, bearophile --------------------- import std.stdio: writeln, write; template IsMutable(T) { enum bool IsMutable = __traits(compiles, { T a; a = T.init; }); } unittest { // of IsMutable(T) auto s1 = "hello1"; static assert( !IsMutable!(typeof(s1[0])) ); char[] s2 = cast(char[])"hello2"; static assert( IsMutable!(typeof(s2[0])) ); } /// ***** NOT tested well enough yet ***** struct IntervalPtr(T) { T* ptr; // can be null debug { private T* start_ptr; // can't be null if present private T* end_ptr; // can't be null if present invariant() { assert(start_ptr != null); assert(end_ptr != null); assert(start_ptr <= end_ptr); assert(ptr == null || (ptr >= start_ptr && ptr < end_ptr)); } } else { this(T* aptr) { this.ptr = aptr; } } this(T* start, T* end) { this.ptr = start; debug { assert(start != null); assert(end != null); assert(start <= end); this.start_ptr = start; this.end_ptr = end; } } this(T* start, T* end, T* aptr) { this.ptr = aptr; debug { assert(end != null); assert(end != null); assert(start <= end); if (aptr != null) { assert(aptr >= start); assert(aptr < end); } this.start_ptr = start; this.end_ptr = end; } } T opStar() { return *this.ptr; } void opPostInc() { debug assert(this.ptr < (this.end_ptr - 1)); this.ptr++; } void opPostDec() { debug assert(this.ptr > this.start_ptr); this.ptr--; } void opAddAssign(size_t i) { debug assert(this.ptr < (this.end_ptr - i)); this.ptr += i; } void opSubAssign(size_t i) { debug assert(this.ptr >= (this.start_ptr + i)); this.ptr -= i; } void opAssign(T* other_ptr) { debug { if (other_ptr != null) { assert(other_ptr >= this.start_ptr); assert(other_ptr < this.end_ptr); } } this.ptr = other_ptr; } void opAssign(IntervalPtr other) { debug { assert(other.start_ptr != null); assert(other.end_ptr != null); assert(other.end_ptr != null); if (other.ptr != null) { assert(other.ptr >= other.start_ptr); assert(other.ptr < other.end_ptr); } this.start_ptr = other.start_ptr; this.end_ptr = other.end_ptr; } this.ptr = other.ptr; } const bool opEquals(ref const(IntervalPtr) other) { return this.ptr == other.ptr; } /*ref ?*/ T opIndex(size_t i) { debug { assert((this.ptr + i) >= this.start_ptr); assert((this.ptr + i) < this.end_ptr); } return this.ptr[i]; } static if (IsMutable!T) { void opIndexAssign(T value, size_t i) { debug { assert((this.ptr + i) >= this.start_ptr); assert((this.ptr + i) < this.end_ptr); } this.ptr[i] = value; } } } IntervalPtr!T intervalPtr(T)(/*inout ?*/ T[] arr) { debug return IntervalPtr!T(arr.ptr, arr.ptr + arr.length); else return IntervalPtr!T(arr.ptr); } IntervalPtr!T intervalPtr(T)(/*inout ?*/ T[] arr, T* aptr) { debug return IntervalPtr!T(arr.ptr, arr.ptr + arr.length, aptr); else return IntervalPtr!T(aptr); } IntervalPtr!T intervalPtr(T)(T* start, T* end) { debug return IntervalPtr!T(start, end); else return IntervalPtr!T(start); } IntervalPtr!T intervalPtr(T)(T* start, T* end, T* aptr) { debug return IntervalPtr!T(start, end, aptr); else return IntervalPtr!T(aptr); } void main() { auto s = "hello"; writeln("String: ", s); auto p1 = s.intervalPtr(); writeln("intervalPtr sizeof: ", p1.sizeof); foreach (_; 0 .. 4) { write(">", *p1, "< "); ++p1; } writeln(">", *p1, "< "); auto p2 = intervalPtr(s.ptr, s.ptr + s.length); foreach (_; 0 .. 4) { write(">", *p2, "< "); p2++; } writeln(">", *p2, "< "); p1 = s.ptr; // p1 reset to the start foreach (i; 0 .. s.length) write(">", p1[i], "< "); writeln(); }
Jan 27 2010
parent reply BCS <none anon.com> writes:
Hello bearophile,

 Matti Niemenmaa:
 
 Your test6 is invalid: it reads beyond the bounds of the given array.
 For example with input "th", it will check whether the third
 character is 'i'; but the length of the array is only 2, so it
 shouldn't be doing that.
 

later. The good thing is that D2 allows me to implement something to catch that kind of out-of-range pointer errors at run-time (D1 is not good enough here).

Things I'd use in place of that: ///// char[] str, int at = 0; ... switch(str[at]) { ... } ... at++; or ///// char[] str; ... switch(str[0]) { ... } ... str = str[1..$]; A good compiler should be able to convert the first to about the same as what your type should compile to. A really good compiler should be able to const propagate at and remove the variable and (if you start by switching on the length) fold out even the bounds checks. The second has the same optimization potential but for some reason I think it would be expecting more of a compiler to get it optimized that well. -- <IXOYE><
Jan 28 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
BCS:

 Things I'd use in place of that:
 
 /////
 char[] str, int at = 0;
 ...
 switch(str[at]) { ... }
 ...
 at++;
 
 or
 
 /////
 char[] str;
 ...
 switch(str[0]) { ... }
 ...
 str = str[1..$];

When in not-debug mode that struct of mine is just 1 word long, so it hopefully gets optimized well by LDC2. While removing that free 2-word ling "str" is a bit harder. With that struct you don't need to carry around two things, a vector and index, you have to keep and move around just one variable. And it acts just like a pointer, so you can move it in both directions, etc (it's not handy nor safe to do this with a slice, you need to keep a 3 words of memory as state to be safe). You can (hopefully) use it as drop-in safer replacement for a pointer that you know spans a range of memory (it can have few holes too), so you can use it in D2 code translated from original C code, changing it very little. You don't want to modify too much that kind of C code. In that broken finite state machine of mine I've had to change just one line of code, where the "p" pointer is defined. With DMD you can remove 100% of the overhead defining it as a pointer in not-debug release, and keeping the rest of the code that use the pointer unchanged. This can be done locally (with a bit more complex pointer definition that defines a true pointer in not-debug mode), or more generally modifying those functions that act as constructors, so they return a true pointer in not-debug mode (but I like this less, I think it's not tidy to have functions that return different types in debug mode). Having safer pointers goes well with the style of D language. Probably I'll put this struct in my future d2libs :-) Maybe with small changes such safe ranged pointers can be used in SafeD modules too :-) Bye, bearophile
Jan 29 2010
parent BCS <none anon.com> writes:
Hello bearophile,

 BCS:
 
 Things I'd use in place of that:
 
 /////
 char[] str, int at = 0;
 ...
 switch(str[at]) { ... }
 ...
 at++;
 or
 
 /////
 char[] str;
 ...
 switch(str[0]) { ... }
 ...
 str = str[1..$];

hopefully gets optimized well by LDC2. While removing that free 2-word ling "str" is a bit harder.

Almost all the cases I can think of fall into one of a few categories: - the length stuff can be statically verified to be correct and the length need not be carried around - the length stuff can't be statically verified but the code handles he dynamic verification in such a way the optimizer can figure out how to safely omit the length checks for much of the code. - the length stuff can't be statically verified and there is no way to enforce correct dynamic verification so you can't safely omit the length and checks even in release mode. In each case, the native solution can be just as fast as your solution or your solution is not safe in release mode.
 And it
 acts just like a pointer, so you can move it in both directions, etc

I'll give you that point. -- <IXOYE><
Jan 29 2010