tag proposal

[dormando]

>     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