Modify GCHashTable to have template parameter for Hashtable value

RESOLVED FIXED

Status

RESOLVED FIXED
8 years ago
8 years ago

People

(Reporter: rulohani, Unassigned)

Tracking

Details

Attachments

(1 attachment, 3 obsolete attachments)

(Reporter)

Description

8 years ago
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.
(Reporter)

Comment 1

8 years ago
Created attachment 464997 [details] [diff] [review]
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.
Attachment #464997 - Flags: superreview?(lhansen)
Attachment #464997 - Flags: review?(treilly)

Comment 2

8 years ago
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.
Attachment #464997 - Flags: review?(treilly) → review+
(Reporter)

Comment 3

8 years ago
(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.
(Reporter)

Comment 4

8 years ago
Created attachment 465359 [details] [diff] [review]
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.
Attachment #464997 - Attachment is obsolete: true
Attachment #465359 - Flags: superreview?(lhansen)
Attachment #464997 - Flags: superreview?(lhansen)

Comment 5

8 years ago
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.)
Attachment #465359 - Flags: superreview?(lhansen) → superreview-
(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

8 years ago
(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.
(Reporter)

Comment 8

8 years ago
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}?
(Reporter)

Comment 9

8 years ago
(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).
(Reporter)

Comment 10

8 years ago
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}...} ]
(Reporter)

Comment 11

8 years ago
> 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.
(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

8 years ago
(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?
(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

8 years ago
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

8 years ago
(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
(Reporter)

Comment 17

8 years ago
Created attachment 466719 [details] [diff] [review]
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?
Attachment #465359 - Attachment is obsolete: true
Attachment #466719 - Flags: superreview?(lhansen)

Comment 18

8 years ago
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.
Attachment #466719 - Flags: superreview?(lhansen) → superreview+
(Reporter)

Comment 19

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

Comment 20

8 years ago
http://hg.mozilla.org/tamarin-redux/rev/26475b6596d8
Status: NEW → RESOLVED
Last Resolved: 8 years ago
Resolution: --- → FIXED

Comment 21

8 years ago
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
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
(Reporter)

Comment 22

8 years ago
Created attachment 469149 [details] [diff] [review]
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+ ?
Attachment #466719 - Attachment is obsolete: true
Attachment #469149 - Flags: review?(treilly)

Comment 23

8 years ago
http://hg.mozilla.org/tamarin-redux/rev/3f5f0e827117
Status: REOPENED → RESOLVED
Last Resolved: 8 years ago8 years ago
Resolution: --- → FIXED

Updated

8 years ago
Attachment #469149 - Flags: review?(treilly) → review+
You need to log in before you can comment on or make changes to this bug.