585694 - Modify GCHashTable to have template parameter for Hashtable value

Status: RESOLVED FIXED

(Tamarin Graveyard :: Garbage Collection (mmGC), defect)

Description

[Ruchi Lohani]

Currently GCHashTable stores the value as const void*. It will be good to modify the hash table such that a template parameter for the hash table value can be used. The use case comes from bug https://bugzilla.mozilla.org/show_bug.cgi?id=554702 where a GCHashTable<Stringp, uint64_t> would have been useful to store 64 bit count values.

Comment 1

[Ruchi Lohani]

Attachment: Initial Patch

Only the value is made a template parameter. Key could be made template parameter the same way. Any suggestions on improving the way hashtable could be declared are welcome. Rightnow these are valid:
MMgc::GCHashtableBase<uint64_t> ht;
MMgc::GCHashtableBase<uint64_t, GCStringHashtableKeyHandler> ht;   //key is char* 
MMgc::GCHashtableBase<uint64_t, GCStringHashtableKeyHandler, GCHashtableAllocHandler_new> ht; etc.

Comment 2

[Tommy Reilly]

Comment on attachment 464997 [details] [diff] [review]
Initial Patch

Looks great.  I would have chosen 3 for the initial value of n on the theory that 0 could lead to clustering but its probably a wash with a good probe function.  I ran the memory profiler on GCBench and it didn't seem to matter either way, that's a really good way to pound on the hashtables btw.

Comment 3

[Ruchi Lohani]

(In reply to comment #2)
> Comment on attachment 464997 [details] [diff] [review]
> Initial Patch
> 
> Looks great.  I would have chosen 3 for the initial value of n on the theory
> that 0 could lead to clustering but its probably a wash with a good probe
> function.  I ran the memory profiler on GCBench and it didn't seem to matter
> either way, that's a really good way to pound on the hashtables btw.

I think initial value of 3 for n will be worse than 0 as the probe sequence will start repeating the already looked up indexes before looking every index once.

If the table size is 8 (say) and the initial index (hash & bitMask) is 3 then the sequence becomes:
3 7 4 2 1 1 2 4 7 whereas with n = 0 it will be 3 4 6 1 5 2 0 7 7.

Comment 4

[Ruchi Lohani]

Attachment: Patch with some useful comments

No code changes. Added some comments for the hash collision quadratic probe. Will be easy to figure out in future whats going on.

Comment 5

[Lars T Hansen]

Comment on attachment 465359 [details] [diff] [review]
Patch with some useful comments

This is probably wrong:

+        VAL ret = 0;

What if VAL is a struct type?

This is definitely wrong:

+            table[i].value = NULL;

It is true that NULL and 0 have the same meaning in pointer contexts but they do not have the same meaning in non-pointer contexts, at least not on all compilers.  You want to use 0 here, although that's may not be correct either for the same reason of the previous issue.

(I should say that you can fix the issue of assigning 0 to a VAL by adding a comment somewhere saying that VAL is restricted to types to which you can assign 0.  I just haven't seen such a comment.)

Comment 6

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #5)
> Comment on attachment 465359 [details] [diff] [review]
> Patch with some useful comments
> 
> This is probably wrong:
> 
> +        VAL ret = 0;
> 
> What if VAL is a struct type?
[...]
> 
> (I should say that you can fix the issue of assigning 0 to a VAL by adding a
> comment somewhere saying that VAL is restricted to types to which you can
> assign 0.  I just haven't seen such a comment.)

One could also consider the alternative initialization:

  VAL ret = {0};

If VAL is a scalar type, then this turns back into "VAL ret = 0;"

If VAL is an aggregate, then this zero-initializes the first member and value-initializes the remaining members (which degenerates into zero-initialization for classes without user-declared constructors). 

This won't cover all possible cases, though, so you'd still need to add a comment specifying which types are legal for VAL.

Comment 7

[Steven Johnson]

(In reply to comment #5)
> This is probably wrong:
> 
> +        VAL ret = 0;
> 
> What if VAL is a struct type?

FWIW, we don't have a current usecase for that.(In reply to comment #6)

> (In reply to comment #5)

> One could also consider the alternative initialization:
> 
>   VAL ret = {0};
> 
> If VAL is a scalar type, then this turns back into "VAL ret = 0;"

Really? I did not know that. If that reliably works on all our compilers, nice win.

Comment 8

[Ruchi Lohani]

Having struct type supported will be good. I tried the {0} initialization. It compiles (on mac) atleast at the location mentioned above. If I try to declare a hashtable of a struct say 'Sample', currently it will throw lots of warnings of uninitialized members from the definition of EMPTY in GCHashtable.h. The {0} doesn't work there. 

How about having  
HashTableEntry(const V & val = V( ), const void * k = NULL)
   : value(val), key(k) { } 

and then using Entry() instead of {0,0}?

Comment 9

[Ruchi Lohani]

(In reply to comment #6)
> (In reply to comment #5)
> > Comment on attachment 465359 [details] [diff] [review] [details]
> > Patch with some useful comments
> > 
> > This is probably wrong:
> > 
> > +        VAL ret = 0;
> > 
> > What if VAL is a struct type?
> [...]
> > 
> > (I should say that you can fix the issue of assigning 0 to a VAL by adding a
> > comment somewhere saying that VAL is restricted to types to which you can
> > assign 0.  I just haven't seen such a comment.)
> 
> One could also consider the alternative initialization:
> 
>   VAL ret = {0};
> 
> If VAL is a scalar type, then this turns back into "VAL ret = 0;"
> 
> If VAL is an aggregate, then this zero-initializes the first member and
> value-initializes the remaining members (which degenerates into
> zero-initialization for classes without user-declared constructors). 
> 

This wont work. It seems to zero-initialize the first member of the struct do nothing for the rest (compiler throws not-initialized warnings for each of the members except the first one).

Comment 10

[Ruchi Lohani]

Setting the table[i].value to zero sounds redundant as we always work with the key to see whether its deleted/equal etc so even if the old value is left in the table, it wont be used (I think) if the key is not valid.

Initializing ret to zero (which is needed) can be done by using VAL ret = VAL().
[ I read this in 
http://books.google.com/books?id=EotSAwuBkJoC&lpg=PA56&dq=zero%20initialize%20a%20template&pg=PA56#v=onepage&q=zero%20initialize%20a%20template&f=false 
Is is this trick worth using? ]

For the EMPTY table initialization issue (Comment 8), what felix suggested on IRC might be ok. [ just using {} instead of { {0,0}...} ]

Comment 11

[Ruchi Lohani]

> This wont work. It seems to zero-initialize the first member of the struct do
> nothing for the rest (compiler throws not-initialized warnings for each of the
> members except the first one).

Forgot to mention that I was working in Xcode.

Comment 12

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #11)
> > This wont work. It seems to zero-initialize the first member of the struct do
> > nothing for the rest (compiler throws not-initialized warnings for each of the
> > members except the first one).
> 
> Forgot to mention that I was working in Xcode.

I was a little confused by the feedback (I could not make comment 9 jibe with comment 10), but I think I understand now.

Here is my attempt to summarize my understanding:

1. It will not work to put "= {0}" as the initializer in both spots.  That is, doing "VAL ret = {0};" and "EMPTY[4] = {0};" does not work; the compiler complains about missing member initializations, as Ruchi notes in comment 9.

2. But, if you keep the change to "VAL ret = {0};", but now use "EMPTY[4] = {}", then things seem to go through swimmingly.

So there's no inherent contradiction here; you have to use the right tool for the right job, and "{0}" is not an appropriate way to initialize the array of Entry structures, but it seems like it may work for initializing the VAL ret.

Comment 13

[Steven Johnson]

(In reply to comment #12)
> 2. But, if you keep the change to "VAL ret = {0};", but now use "EMPTY[4] =
> {}", then things seem to go through swimmingly.

Waitaminit... I wouldn't have thought that "LHS = {};" is valid C++ in any way shape or form. Really?

Comment 14

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #13)
> (In reply to comment #12)
> > 2. But, if you keep the change to "VAL ret = {0};", but now use "EMPTY[4] =
> > {}", then things seem to go through swimmingly.
> 
> Waitaminit... I wouldn't have thought that "LHS = {};" is valid C++ in any way
> shape or form. Really?

My understanding is that it is legal in standard C++ but not in standard C.

I don't have a copy of the C standard handy.  But if you look in the C++ 2003 ISO standard, in 8.5.1 items 4, 7 and 8 the standard discusses empty initializer lists.

I'm not actually convinced that we're really saving ourselves any grief by making use of this "feature" though.  We might be setting ourselves up for a tarpit later if someone starts making use of this and then we decide we don't want to support it any more.  I certainly wouldn't object if we just went with Lars' original suggestion of sticking with a direct 0, no curly braces adorning it, along with a comment saying what this means about which specializations are legal for VAL.

Comment 15

[Lars T Hansen]

If there's no current use case for structs then I vote we add a comment to the effect that it's not supported, make the assignments "= 0", and ship it.  Sometimes (frequently?) the less general solution is the better one.

Comment 16

[Steven Johnson]

(In reply to comment #15)
> If there's no current use case for structs then I vote we add a comment to the
> effect that it's not supported, make the assignments "= 0", and ship it. 

+1

Comment 17

[Ruchi Lohani]

Attachment: Updated patch

Added comment for the kind of values being supported currently in the hash table.
Leaving the task of making it generic for future. Should I file a bug for that or just leave it for the person who might need it in future?

Comment 18

[Lars T Hansen]

Comment on attachment 466719 [details] [diff] [review]
Updated patch

I don't think it's necessary to file a bug for the generalization; with the compile error and the comment it will be obvious to future generations that the job is still to be done.

Comment 19

[Ruchi Lohani]

Lars/Steven/Tommy, can you push this for me? Thanks.

Comment 20

[Tommy Reilly]

http://hg.mozilla.org/tamarin-redux/rev/26475b6596d8

Comment 21

[Tommy Reilly]

Backed out, solaris, win64 and win-arm  aren't happy.

Log(s) of failed build steps:
 Slave: solaris-sparc-compile
       Build_Release
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/solaris-sparc-compile/builds/310/steps/Build_Release/logs/stdio

       Build_Release-wordcode
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/solaris-sparc-compile/builds/310/steps/Build_Release-wordcode/logs/stdio

       Build_Debug
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/solaris-sparc-compile/builds/310/steps/Build_Debug/logs/stdio

       Build_ReleaseDebugger
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/solaris-sparc-compile/builds/310/steps/Build_ReleaseDebugger/logs/stdio

       Build_DebugDebugger
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/solaris-sparc-compile/builds/310/steps/Build_DebugDebugger/logs/stdio

       Build_Check
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/solaris-sparc-compile/builds/310/steps/Build_Check/logs/stdio

 Buildsteps that were failing before this build:
   Compile_builtin.abc Revision: 4914 Blamelist: Chris Peyer
   Build_Release Revision: 5102 Blamelist: Tommy Reilly
   Build_Release-wordcode Revision: 5102 Blamelist: Tommy Reilly
   Build_Debug Revision: 5102 Blamelist: Tommy Reilly
   Build_ReleaseDebugger Revision: 5102 Blamelist: Tommy Reilly
   Build_DebugDebugger Revision: 5102 Blamelist: Tommy Reilly
   Build_Check Revision: 5102 Blamelist: Tommy Reilly

 Slave: winmobile-emulator-compile
       Build_ReleaseARM
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/winmobile-emulator-compile/builds/393/steps/Build_ReleaseARM/logs/stdio

       Build_Release-wordcode-ARM
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/winmobile-emulator-compile/builds/393/steps/Build_Release-wordcode-ARM/logs/stdio

       Build_Release-fpu-ARM
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/winmobile-emulator-compile/builds/393/steps/Build_Release-fpu-ARM/logs/stdio

       Build_DebugARM
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/winmobile-emulator-compile/builds/393/steps/Build_DebugARM/logs/stdio

       Build_Debug-fpu-ARM
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/winmobile-emulator-compile/builds/393/steps/Build_Debug-fpu-ARM/logs/stdio

       Release64
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/winmobile-emulator-compile/builds/393/steps/Release64/logs/stdio

       Release-wordcode64
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/winmobile-emulator-compile/builds/393/steps/Release-wordcode64/logs/stdio

       Debug64
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/winmobile-emulator-compile/builds/393/steps/Debug64/logs/stdio

       ReleaseDebugger64
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/winmobile-emulator-compile/builds/393/steps/ReleaseDebugger64/logs/stdio

       DebugDebugger64
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/winmobile-emulator-compile/builds/393/steps/DebugDebugger64/logs/stdio

       Build_Check
       http://tamarin-builds.mozilla.org/tamarin-redux/builders/winmobile-emulator-compile/builds/393/steps/Build_Check/logs/stdio

Comment 22

[Ruchi Lohani]

Attachment: Fix compile time errors

Fixed problems which failed the build on several platforms. Ran a sandbox build on my sandbox branch. Tommy, can you push it when its reviewed+ ?

Comment 23

[Tommy Reilly]

http://hg.mozilla.org/tamarin-redux/rev/3f5f0e827117