[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Ideas about implementing a string type?
- From: Rici Lake <lua@...>
- Date: Thu, 29 Mar 2007 15:57:11 -0500
David Kastrup wrote:
"Jerome Vuarand" <jerome.vuarand@ubisoft.com> writes:
David Kastrup wrote::
Rici Lake <lua@ricilake.net> writes:
and a few probes into the intern table all of which will quickly
return "unequal". However, copying a million bytes (say) is time
consuming.
I doubt that million byte strings are the norm. And I doubt that
you'll _ever_ be in the situation that million-byte strings will be
used for comparison or indexing, and thus the whole hashing operation
is a waste of time.
That's true, but it's negligible compared to whatever else you did to
create strings of length one million.
Mike Pall's suggestion about benchmarking is well thought out, but I'm
also too lazy to do it. However, I did do a little microbenchmark of
copying versus hashing for different string lengths. The code (and
the small patch to lstring.c to expose the hash function) are below
so you can try it yourself. I should add that gcc does a pathetic job
of "optimizing" memcpy in this particular case, and that compiling
both lua and the benchmark without optimization actually results in
faster timings for the copy and luapush cases; I'll leave it
to others to test that in more realistic settings on different
compilation environments.
The benchmark program creates a buffer of size 2n of pseudorandom
characters, and then successively does some operation substrings
of length n of the buffer. The things I tested were:
donothing: base case, does nothing but create the buffer.
hashonly: calls into lstring.c to compute the hash
copyonly: memcpy's the string into a buffer
luapush: pushes and pops the string from the Lua stack
I computed the data for this chart by using the command:
$ for len in 124 7145 21583; do for x in donothing hash copy lua ; do
time ./benchmark $x 1000000 $len ; done; done
That performs the test a million times on various lengths pulled
out of a hat. I condensed the data by reporting only user time. It's
not a very good benchmark but it was the best i could do in a few
minutes:
length donothing hashonly copyonly luapush
124 0m0.008s 0m0.116s 0m0.056s 0m0.724s
7145 0m0.008s 0m0.120s 0m5.660s 0m7.468s
21583 0m0.012s 0m0.116s 0m18.061s 0m19.709s
So, for shortish strings, hashing takes about twice as long as a copy
(an order of magnitude in base 2, I guess) but as strings get longer,
the time is dominated by copying; for strings of length 21583, which
are possibly more common than million-byte strings, the copying takes
more than 100 times long, which is orders of magnitude in base 10.
The luapush case is interesting, because in that case (only), the
copy is being malloc'd and later free'd, as well as the garbage
collector running from time to time. (I didn't control for those
effects.) It appears that this is the dominant cost for short strings,
but for longer strings the dominant cost is the cost of (ahem) copying.
:)
Code follows. I know it makes the message long, but I strong believe
that benchmarks ought to be reproducible. Perhaps I did something
really dumb. First is the patch to lstring.[ch] and then the
benchmark program itself, which was compiled on gcc 4.1.1 with
the command:
gcc -Wall -O3 -g -o benchmark benchmark.c -L. -llua -lm
--------
diff -ur ../lua-5.1.1/src/lstring.c src/lstring.c
--- ../lua-5.1.1/src/lstring.c 2005-12-22 11:19:56.000000000 -0500
+++ src/lstring.c 2007-03-29 15:27:56.000000000 -0500
@@ -72,6 +72,16 @@
}
+unsigned int luaS_hashstr (lua_State *L, const char *str, size_t l) {
+ unsigned int h = cast(unsigned int, l); /* seed */
+ size_t step = (l>>5)+1; /* if string is too long, don't hash all its
chars */
+ size_t l1;
+ for (l1=l; l1>=step; l1-=step) /* compute hash */
+ h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
+ return h;
+}
+
+
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
GCObject *o;
unsigned int h = cast(unsigned int, l); /* seed */
diff -ur ../lua-5.1.1/src/lstring.h src/lstring.h
--- ../lua-5.1.1/src/lstring.h 2005-04-25 14:24:10.000000000 -0500
+++ src/lstring.h 2007-03-29 15:28:06.000000000 -0500
@@ -27,5 +27,6 @@
LUAI_FUNC Udata *luaS_newudata (lua_State *L, size_t s, Table *e);
LUAI_FUNC TString *luaS_newlstr (lua_State *L, const char *str, size_t l);
+unsigned int luaS_hashstr (lua_State *L, const char *str, size_t l);
#endif
----
rici@rici-desktop:~/src/strtest$ cat src/benchmark.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "lua.h"
#include "lauxlib.h"
#include "lstring.h"
/* Test: generate ntrial strings of size length. For each string,
* call the function, and then free the string
*/
typedef void (*Testfunc)(void *, const char *, size_t);
static void benchmark (int ntrial, size_t length, Testfunc func, void *ud) {
unsigned char *buffer = malloc(length*2);
int i;
int offset = 0;
assert(buffer);
for (i = 0; i < length*2; ++i) buffer[i] = (rand() & 0x255U);
for (; ntrial > 0; --ntrial) {
func(ud, (char *)(&buffer[offset]), length);
offset = offset < length ? offset + 1 : 0;
}
free(buffer);
}
static void donothing (void *ud, const char *s, size_t length) {
(void*)ud;
(const char*)s;
(size_t)length;
}
static void hash (void *ud, const char *s, size_t length) {
luaS_hashstr((lua_State *)ud, s, length);
}
static char *copy_buffer = NULL;
static void copy (void *ud, const char *s, size_t length) {
if (copy_buffer == NULL) { copy_buffer = malloc(length);
assert(copy_buffer); }
memcpy(copy_buffer, s, length);
}
static void push (void *ud, const char *s, size_t length) {
lua_pushlstring((lua_State *)ud, s, length);
lua_pop((lua_State *)ud, 1);
}
typedef struct { const char *name; Testfunc func; } Reg;
static const Reg funcs[] = {
{"donothing", donothing},
{"hashonly", hash},
{"copyonly", copy},
{"luapush", push},
{NULL, NULL}
};
int main (int argc, char **argv) {
const char *funcname = "donothing";
void(*func)(void *, const char *, size_t) = donothing;
int ntrial = 10000;
size_t length = 7145;
lua_State *L = lua_open();
const Reg *reg;
assert(L);
if (argc > 1) {
funcname = NULL;
for (reg = funcs; reg->name; ++reg) {
if (argv[1][0] == reg->name[0]) {
funcname = reg->name;
func = reg->func;
break;
}
}
}
if (argc > 2) ntrial = atoi(argv[2]);
if (argc > 3) length = atoi(argv[3]);
if (funcname && ntrial && length) {
printf("%-10s: %6d trials of length %6d\n", funcname, ntrial,
(int)length);
benchmark(ntrial, length, func, (void *)L);
}
else {
char c = '[';
printf("Usage: %s ", argv[0]);
for (reg = funcs; reg->name; ++reg) {
printf("%c%s", c, reg->name);
c = '|';
}
printf("] ntrial length\n");
exit(1);
}
return 0;
}
