My guess is that it was set up this way since the difference in size between 1-10 is negligible, and creating a hash as small as under 10 elements can yield terrible performance. @asterite do you want to chime in?

The capacity must always match values in HASH_PRIMES to get less hash collitions, if I remember correctly

However, it's OK to raise an ArgumentError if the capacity is negative. And I guess we should cap the initialize capacity to one of the prime values (right now that's not the case), though I'm not sure that's really needed.

Cap the initial capacity to one of the primes, or actually try to match it to the closest largest one? For instance, if a user creates a hash with initial capacity 12, should we actually create a hash with size 19?

I don't know... A hash literal will set the initial capacity to the number of elements it has. If the initial capacity is less than what is passed there will be a rehash of all the values, which is not good. So I think using a larger value is better.

Ok, then we should:

• Create an issue to use the next largest prime instead of the actual inicial capacity set by the user
• Kindly ask @dylandrop to keep the original if < 11 then 11, and submit this PR with the exception on negative capacity only

Agree?

Kindly ask @dylandrop to keep the original if < 11 then 11, and submit this PR with the exception on negative capacity only

Happy to do this, but want to add: I think we should at least warn the user about this rule with a message. Or, I can add documentation for it.

I'd avoid a warning on runtime for that, but I agree on adding it to the documentation; however, I'd wait to define whether we want to just keep the current behaviour, or go for always using the next largest prime.

We went through the Ruby implementation, and it seems that when a capacity is passed in, Ruby looks for the largest power of 2 smaller than the requested value, and uses the prime generated from that power of 2 as the actual capacity. See here for the code.

I'd suggest we copy that implementation, and add a notification about it on the docs as @dylandrop suggested; as well as raise the exception if the capacity is negative.

@dylandrop this is actually exceeding the original scope of this PR. Would you like to add this implementation here, or would you rather close this PR and we open a new issue for you or someone else to work on it?

@spalladino No I can take care of it -- seems reasonable.

@spalladino @asterite Alright, we're good for another look.

Interesting, it seems from the Travis build that using this approach leads to some very large memory allocation, causing the process to crash. I'm wondering if I should just use the size the caller passed in if the passed size exceeds a certain value (say 8192 + 27).

Or, perhaps there's some bug in my code I'm not seeing.

Output at the bottom of the Travis job:

GC Warning: Repeated allocation of very large block (appr. size 268439552):
	May lead to memory leak and poor performance
GC Warning: Repeated allocation of very large block (appr. size 268439552):
	May lead to memory leak and poor performance
GC Warning: Repeated allocation of very large block (appr. size 1073745920):
	May lead to memory leak and poor performance
GC Warning: Repeated allocation of very large block (appr. size 2147487744):
	May lead to memory leak and poor performance
GC Warning: Repeated allocation of very large block (appr. size 33558528):
	May lead to memory leak and poor performance
GC Warning: Repeated allocation of very large block (appr. size 67112960):
	May lead to memory leak and poor performance
GC Warning: Repeated allocation of very large block (appr. size 134221824):
	May lead to memory leak and poor performance
GC Warning: Repeated allocation of very large block (appr. size 268439552):
	May lead to memory leak and poor performance

For now I thinking about another implementation of Hash itself, using open addressing and powers of two.

Ruby 2.4 increases its Hash performance for 10-200% with this change (see https://bugs.ruby-lang.org/issues/12142#note-142 for details).

@akzhan I'm sure a PR using open addressing would be accepted, it's been discussed a few times for sure. However that's pretty irrelevant to this current issue.

Just asked @funny-falcon for some details (its implementation looks cleaner for me).

I'd be happy to make PR with open-addressing implementation.
Though I'm not very organized man. So if i will not create PR within 3 weeks, better do it yourself.

@funny-falcon Feel free to publish clean idea implemented in C++14, it's easy to convert good C++ code to Crystal.

See this blog post when implementing a hash table: http://www.idryman.org/blog/2017/05/03/writing-a-damn-fast-hash-table-with-tiny-memory-footprints/

Also make sure to read the HN comments and the references at the end of the article. There's a load of good resources.

@RX14 , I will try to reimplement same approach, used for Ruby. Perhaps it is not the best.

I think, there could be concurrent PR with different implementations, so you can implement other one.

@akzhan , there is interest to use C++ :-) I don't know Crystal well yet, so it will be good reason to learn more.
Edit: there is no interest to use C++.

@funny-falcon Please mention #4557 as base issue for pull request, thanks.

This has been fixed in #8017