A singly linked list should be sufficient. The structs could be
reused, but the actual tags themselves do need to be allocated at some
point. I don't know how important that allocation is to avoid.
(Duh, sorry. I should've just said linked list instead of vague
struct/this/that).
Allocations aren't bad if they're not happening constantly. I guess if
someone's going to have one tag per item you'd end up doing a malloc per
store anyway, which is bad...
I meant 8 bytes per item overhead in general. The counter and the
pointer. Whether the pointer is a linked list or an array, the overhead
is fixed for non-tag users.
Duh, again.
Tag support could probably be a config (not ./configure) option
though, and avoid that memory overhead.
That feels messy, but it could be made to work.
IMHO territory, but I like ./configure'ing new experimental features,
and config'uring stable ones. Makes more sense for people who want to
use packages, which ends up being a lot.
When do we need locks?
I admit I'm a bit weak when it comes to threading in C, but when
threading, I'd think the global counter should be something that doesn't
get cached and where the increment is atomic.
Are increments atomic across SMP/multicore? It'd be hard to corrupt it,
but I don't know off the top of my head if it's safe to ignore locking
when you're just reading/writing to one set of 4-8bytes. I'll have to
read up (or hope someone who knows better about this use of memory
barriers chimes in. It's not something I deal with much outside of
tracking down kernel bugs on SMP systems).
The hashtable itself can at worst have a lock per bucket. There's
an implementation of a lock-free hashtable in java that should be
possible in C as well. Perhaps we could just leave this optimization to
those who need it since the overlap between people who really need MT
and people who really wants tags seems to be quite small so far. :)
Hah. Biglock the hash table, let someone who needs it fix it? :) Dirty,
but I can't complain.
-Dormando
