search

dmolik / xxhash

Automatically exported from code.google.com/p/xxhash
Other
0 stars 0 forks source link

Patch to avoid any heap allocations #9

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
At the moment, the API that uses a state, to allow incremental hashing, will 
require a malloc/free call. I adapted that to avoid this. The drawback is, that 
the state is now in the "public API", which means on state layout changes, you 
can't stay BC, which I guess is no real problem. For my use case, where I need 
the incremental version to hash multiple members at once, this removes the 
stalls by malloc/free (which vary depending on your system malloc/malloc 
replacement).

Feel free to use the patch, I am ok with your licensing. Perhaps others have 
the same issues.

Original issue reported on code.google.com by christop...@gmail.com on 21 May 2013 at 6:34

Attachments:

GoogleCodeExporter commented 9 years ago 
Hmm, wanted to mark this as "enhancement", but guess either I am not allowed to 
do so now or I am to dumb ;)

Original comment by christop...@gmail.com on 21 May 2013 at 6:36

GoogleCodeExporter commented 9 years ago

Original comment by yann.col...@gmail.com on 21 May 2013 at 6:44

GoogleCodeExporter commented 9 years ago 
Hi Christoph,

avoiding malloc/free is a pretty nice idea overall,
however I also don't really like to publish an internal structure into public 
space. It tends to add risks for code maintenance of user programs. So I'm not 
sure which problem is worst.

Note that latest version of xxHash allows both external allocation and re-use 
of memory state, through these new functions :
int           XXH32_sizeofState();
XXH_errorcode XXH32_resetState(void* state_in, unsigned int seed);

Could they help for your use-case ?

Regards

Original comment by yann.col...@gmail.com on 21 May 2013 at 6:55

GoogleCodeExporter commented 9 years ago 
With XXH32_sizeofState() you still can not really put this on the stack (beside 
if you use alloca), which is the fastest and simplest way to allocate. 

Still, I can understand you concerns. In C, there is really no simple way to 
avoid that people might mess with the content of the state struct and try to 
rely on some vars/behaviour there...

You could create some equal layouted dummy struct for the public API, still, 
that is a big hack.

Original comment by christop...@gmail.com on 21 May 2013 at 7:02

GoogleCodeExporter commented 9 years ago 
As far as hacks are concerned, it's also possible (for example) to allocate 
some memory on the stack, typically with a table of chars, check if the size is 
large enough with XXH32_sizeofState(), and then provide this space as void* to 
further xxHash functions, such as XXH32_resetState().

It's certainly an ugly hack, but since it is on user side, it means the user 
must be aware of the risks/consequences for future code maintenance (the main 
one being, should XXH32_sizeofState() increase, better have a clean error code).

Original comment by yann.col...@gmail.com on 21 May 2013 at 8:24

GoogleCodeExporter commented 9 years ago 
Ok, using the latest version, I can tailor that hack around using some static 
sized struct with right alignment on the stack and checking once at startup 
that it is still large enough calling the XXH32_sizeofState function.

That is ok for me, I need not to patch your sources then, which is nice ;)

Have no problem if you close this request.

Only note from my side: you now have three extra functions, the sizeof, the 
reset and the intermediate digest, which you could all remove if you would 
expose either the internal or just a dummy struct with the right size. I guess 
that would cause less possible misuse as that functions ;)

Thanks anyway for a really nice hash function! You rock!

Original comment by christop...@gmail.com on 21 May 2013 at 10:25

GoogleCodeExporter commented 9 years ago 
> Have no problem if you close this request.

ok

> you now have three extra functions, the sizeof, the reset and the 
intermediate digest, which you could all remove if you would expose either the 
internal or just a dummy struct with the right size

Not sure if it would be enough.
sizeofState() is the most likely to become irrelevant, although the basic 
assumption is that the user code will be recompiled with each revision of 
xxHash, and not simply linked into some kind of DLL.

But reset() is still necessary. Reset() is more than a simple memset(), all 
variables need to be properly setup, so this function is really necessary.
But maybe you mean that there would be no need for separate init() and reset() ?
In this case you are right, since init() is merely a malloc() followed by a 
reset().

Same thing for intermediateDigest() : digest() is merely an 
intermediateDigest() followed by a free(). So if free() becomes useless, 
obviously...
Note btw it's already possible to free() directly on the state pointer, without 
using the final digest().

Original comment by yann.col...@gmail.com on 21 May 2013 at 11:30

GoogleCodeExporter commented 9 years ago 
The requested use-case seems realizable using the current interface.

Original comment by yann.col...@gmail.com on 21 May 2013 at 11:32

GoogleCodeExporter commented 9 years ago 
Hi guys !
Thanks to Yann, I was able to notice this issue.
And sorry for too late reply.

I think there are a few minor problems about fundamental requirement.

(1) Environment: Freestanding vs Hosted.
I know originally Yann designed xxhash library for hosted
environment which has a heap memory manager (malloc/free).
But since introducing resetState() etc, xxhash had a chance to
support freestanding environment.
Cristoph's proposal (state exposure) favor this trend more complete.

(2) Assertion: Runtime vs Compile-Time.
By following the comments of this issue, we can raise runtime
assertion about sizeofState() mismatch.
But, it would be nice to see some kind of compile-time
assertion (eg. static_assert()).

Possible Solutions:

(A) Do nothing.
Since xxhash is small, users could maintain their own hacks easily.

(B) Define version (revision) symbol.
With this symbol, user can raise compile-time assertion.

--- xxhash.h ---
#define XXHASH_VERSION 100
--- xxhash.h ---

--- my-own-code.c ---
#if !defined(XXHASH_VERSION) || (XXHASH_VERSION > 100)
#error Unknown xxhash version. Please check sizeof(XXH_state32_t).
#endif
--- my-own-code.c ---

(C) Add detail header for limited exposure and configuration.
For example, add xxhash_detail.h and declare/define some symbols.

--- xxhash_detail.h ---
...
//#define XXH_ACCEPT_NULL_INPUT_POINTER 1
//#define XXH_FORCE_NATIVE_FORMAT 1

#if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L
# include <stdint.h>
...
#endif

struct XXH_state32_t { ... };
...
--- xxhash_detail.h ---

Basically, this header is for implementor (Yann himself) but
also for advanced users who understand what they do at their own risk.

Original comment by takayuki...@gmail.com on 29 May 2013 at 5:32

GoogleCodeExporter commented 9 years ago 
Freestanding environment seems a quite difficult goal to integrate.
I guess it would be necessary to remove all dependencies to malloc()/free(),
effectively modifying the interface contract.

As a middle ground, it's possible to make the memory related functions 
user-definable,
well if it makes sense for anyone...

Original comment by yann.col...@gmail.com on 29 May 2013 at 11:22

GoogleCodeExporter commented 9 years ago 
If you really want to support malloc/free "free" environments I still think the 
least ugly way is to just expose the state struct and change the methods like I 
proposed. Document the members of the state as "keep fingers away" and be done. 
Only drawback is that you will be BIC as soon as you change the layout/size of 
the struct.

Original comment by christop...@gmail.com on 29 May 2013 at 11:28

GoogleCodeExporter commented 9 years ago 
The attached file is a proposed solution for requested malloc-averse 
environments.

On top of existing XXH32_sizeofState() function,
a new constant is provided, XXH32_SIZEOFSTATE.

The value of this constant is checked at compile time, 
and trigger a compilation error if it is not big enough.
(You can try it by modifying the constant to a smaller value).
I've authorized larger values in the static assert declaration, since it causes 
no problem, although stricter requirement could be enforced if need be (==).

This exercise also made me arrange variables inside the structure differently, 
saving a few bytes in the process.

Regards

Original comment by yann.col...@gmail.com on 29 May 2013 at 5:45

Attachments:

GoogleCodeExporter commented 9 years ago 
simpler version (but functionally identical)

Original comment by yann.col...@gmail.com on 29 May 2013 at 8:06

Attachments:

GoogleCodeExporter commented 9 years ago 
With the define, I can allocate statically on the stack, which is very nice.
Problem here might be alignment, e.g. if I now do:

char my_state[XXH32_SIZEOFSTATE];

and use this for the hashing functions, the ints might be horrible wrong 
aligned on some platforms which can either only degenerate performance or lead 
to misalignment exceptions ;)

I am really not sure if the pure size exposure is a such good idea ;)

Original comment by christop...@gmail.com on 30 May 2013 at 11:53

GoogleCodeExporter commented 9 years ago 
Hey, that's a good point.
Alignment of internal fields can be pretty important, depending on target 
system.

Original comment by yann.col...@gmail.com on 30 May 2013 at 12:21

GoogleCodeExporter commented 9 years ago 
There's a convoluted way to ensure the state is properly aligned.
For example, if Size=48, and alignment=8,

char stateSpace[55];  // 55 = 48 + 8 - 1
void* state = (void*)((stateSpace + 7) & 0xFFFFFFF8);  // 7 = 8 - 1 ; 
0xFFFFFFF8 = -8

But that's a bit complex.
But maybe this could be hidden in a macro ?

Original comment by yann.col...@gmail.com on 30 May 2013 at 12:37

GoogleCodeExporter commented 9 years ago 
:) I am not that sure if that is really better than just moving the struct in 
the header and adding a comment that the internal fields are subject to change 
;)
Even with only the define the interface will change if the struct size changes.

Original comment by christop...@gmail.com on 30 May 2013 at 12:42

GoogleCodeExporter commented 9 years ago 
No it won't, since the macro will use XXH32_SIZEOFSTATE. 

But anyway, I get the point : this is becoming more complex than merely 
publishing the state internal structure.

Original comment by yann.col...@gmail.com on 30 May 2013 at 12:52

GoogleCodeExporter commented 9 years ago 
[deleted comment]
GoogleCodeExporter commented 9 years ago 
XXH_malloc(), XXH_STATIC_ASSERT() looks good.

For the alignment, should we also change the malloc() call in XXH32_init() ?

For the padded array placeholder, I think it will cause strange behaviour.
Please see this example (alignment-offset-test.cpp): http://ideone.com/qmEsI2

In this example, we have two MyStruct and copy c to d.
But their alignment offset is different, so copy will (logically) fail
and maybe hard to recognize what happened.

Adding dedicated copy function will fix this problem, but I don't know
it is worth for it.

Hmm, it seems just a bit complicated :(

Original comment by takayuki...@gmail.com on 30 May 2013 at 6:17

Attachments:

GoogleCodeExporter commented 9 years ago 
> For the alignment, should we also change the malloc() call in XXH32_init() ?

I don't think so, since
malloc() tends to do a fine job when it comes to alignment.
In my tests, malloc() allocates memory blocks based on cache line access, which 
are multiple of 64.

I guess it is potentially possible that a bad malloc() implementation on some 
specific system results in unaligned fields within the struct, but this is 
quite unlikely, and I wish to avoid making the generic code heavier to support 
specially rare corner cases. I think that's what forks are for.

> For the padded array placeholder, I think it will cause strange behavior.

OK, right,
I was thinking about defining the state as a multiple of long long.
This would ensure allocation to be properly aligned on multiple of 8.
All this would be hidden behind a macro XXH32_CREATESTATE_ONSTACK(stateName).

However, as said by Christoph, it ends up being more complex than just 
publishing the internal state. 
I feel uneasy about this decision, but I must admit alternatives are not 
clearly better so far.

Original comment by yann.col...@gmail.com on 30 May 2013 at 6:58

Attachments:

GoogleCodeExporter commented 9 years ago 
OK, last attempt.

This version is providing both a typedef'd struct and a macro
to statically allocate state (typically on stack)
and ensure proper alignment on 8-bytes boundaries.

Hope the naming is correct.

Original comment by yann.col...@gmail.com on 31 May 2013 at 3:33

Attachments:

GoogleCodeExporter commented 9 years ago 
I am more than happy with that ;) I can use it now unpatched with pure 
stack-allocations.

Original comment by christop...@gmail.com on 31 May 2013 at 6:04

GoogleCodeExporter commented 9 years ago 
Looks good !

Just trivial things for further refinement.

(1) We should not assume sizeof(long long) == 8,
since xxhash supports older compilers.
Even C99, we could assume sizeof(long long) >= 8.

So we should not use constant '8'.

(2) XXH32_stateSpace_t is not strictly aligned to 8-bytes.
It is sufficiently aligned for access with long long.

For example, compile attached file by MSVC++2012 for Win32 target with
/Od or /O1 option (aka Debug build). MSVC++2012 treats sizeof(long long) == 8,
but you will see 4-bytes aligned long long structure on stack.

Original comment by takayuki...@gmail.com on 31 May 2013 at 3:48

Attachments:

GoogleCodeExporter commented 9 years ago 
Thanks for very useful input.

(1) Source code is corrected, using sizeof(long long) instead of 8

(2) If the allocation is sufficiently aligned to access long long, then it 
respects the most important condition. It's good enough for xxHash.

The version in attached file reflects both your recommendations.

The macro name was changed to XXH32_STATIC_ALLOCATE_STATE(), to have a more 
generic feel.

Original comment by yann.col...@gmail.com on 31 May 2013 at 4:03

Attachments:

GoogleCodeExporter commented 9 years ago 
Both changes looks good !

But, why should we not use XXH32_stateSpace_t directly ?

Original comment by takayuki...@gmail.com on 2 Jun 2013 at 2:25

GoogleCodeExporter commented 9 years ago 
It's certainly not forbidden.

Do you mean, you feel macro XXH32_STATIC_ALLOCATE_STATE() is not really helpful 
?

Original comment by yann.col...@gmail.com on 2 Jun 2013 at 7:07

GoogleCodeExporter commented 9 years ago 
Yes, I think so.

For any type of pointer (which have same cv-qualifier),
implicit cast to void * is valid in any version of C/C++.

So I feel automatic pointer casting helper is doing
the same thing as compiler.

Original comment by takayuki...@gmail.com on 3 Jun 2013 at 9:56

GoogleCodeExporter commented 9 years ago 
ok

Original comment by yann.col...@gmail.com on 3 Jun 2013 at 11:20

GoogleCodeExporter commented 9 years ago 
done in r30

Original comment by yann.col...@gmail.com on 4 Jun 2013 at 12:06