Worse problem: doesn't look it is faster :-(
While some microbenchmarks I've made shows it is a bit faster, http helloworld is slower, and std_spec is also a bit slower.

And 32bit compiler test didn't pass in Travis-CI.

Looks like, reallocation costs too much.
Probably could be better if entries are allocated by chunks instead of by huge array.
I'll close this PR now until improving.

I think that Hash may have two different implementations for small (<7) and other sizes.

I'm sure that small hashes have a big value.

I benchmarked this PR and it works twice as fast as the current Hash. Here's my benchmark:

a = {} of Int32 => String

strings = Array.new(10_000_000, &.to_s)

time = Time.now
strings.each_with_index do |s, i|
  a[i] = s
end
puts Time.now - time

Remember to run this with bin/crystal in master and bin/crystal with your branch, so we are sure both use funny hash.

It would be interesting to see your benchmarks.

I think this Hash should be more efficient because in the current Hash every time you add a key-value pair there's an allocation for the node. In your implementation that doesn't seem to be the case.

It is expected for single huge hash to be faster.

But http helloworld ( from crystal-lang.org main page) prouces many small hashes.

Testing compiler compile performance (with --no-codegen) before and after is likely to be a good indicator of whether this hash is better just in theory or in practice. Microbenchmarks are only so useful.

I don't like the idea of having a rigid cutoff point with 2 different hash implementations. There must be a way to make it fast at any size.

Another optimization I would love to make is having only 1 malloc call for am empty hash, as at least in the rust compiler I know they found that hashtables being created, never used, but discarded was fairly common.

I have an idea to use chunked allocaion, ie allocate by chunks of 8 entries.
Probably it will be faster than current hash implementation, and not too slower than this PR on huge hashes. I will investigate it.

@funny-falcon Assuming that a larger chunk size would increase performance, you could change chunk size based on the size of the hash to keep the memory overhead bounded when small and performance overhead miniscule when large.

What about implementation of pessimistic downsize politics?

@akzhan , what do you mean?

That was already in this patch: it resized down only if size < capacity / 4

Looks like chunked version is not slower than current implementation even on http hello world, so that I reopen pull request.

@funny-falcon Please give us some documentation on how this works to work with!

Is it GTG?

It plays bad with conservative GC on 32 bit platform:

• stored hashsum could be counted as pointers (failed weakptr test on travis ci). That is why in first version I stored hashsums in separate array (GC then knows to not look inside).
• index array is five-ten times greater than bins in current implementation. Looks like GC doesn't like such big arrays.

So, while small scripts will still work, larger applications become less reliable on 32bit platform with this patch.

So, if support of 32 bit platform is important, this patch should be improved. I don't know, how it should be done. I'm still thinking.

Doubtfuly Crystal will gain precise GC soon.

Have you seen #5271?

@akzhan, not totally clear if anyone can or wants to push that forward ATM though.

I wouldn't focus on the performance of 32-bit too much, but it should work and be stable. 32bit is almost obsolete on x86, but on arm it'll still be a while until 32bit SoCs stop being sold.

32bit version works. It just doesn't play well with conservative GC.

I may make 32bit version more "workable" by not storing hash-sum, and changing it to closed addressing/chained version. I think, a lot of code will be common between 32bit and 64bit versions, so they will co-exists in one file with several if flag?(:32bit).

Perhaps seperating the "implementation-specific" and "helper-methods" parts of hash.cr could keep it more organised. Keep the implementation-specific methods which are changed by this PR at the bottom of the file, and everything else above the file. We can then have a big comment which explains the implementation halfway down the file before all the implementation.

This Pull request is alone that not yet finished anf merged with inspiration of #4675, what is it's state now?

I was a bit busy with work and family. I plan to spend some time on weekends.

damn :-( now 64bit version fails with "Repeated allocation of very large block"... I can't understand, why ;-(

And I can't reproduce on my notebook :-( My version of libgc doesn't complain against. As well as circleci.

Can you ask @ivmai about strange "Repeated allocation of very large block"?

I thought the repeated allocation was just a warning. I get that in my implementation too.

EDIT: Or well, it is not really 'just' a warning as stuff like this shouldn't warn, but not an error.

No, the error is that the compiler specs ran out of memory. Check the usage before and after locally.

Problem is I cann't reproduce. And circleci cann't as well. So, looks like it depends on hosts libgc.

I have one suggestion: probably it is because old code doesn't reallock huge bins array on #clean . But to check I need refactor code.

I turned off deallocation on clear, but looks like it doesn't help.
I don't know what to do further :-(

@funny-falcon it's unlikely to be a libgc bug. You probably can't reproduce it simply because you have more ram than the travis VM. Look at your ram usage when running make compiler_spec before and after this PR.

@RX14, I don't claim it is libgc bug. I've said, libgc behaves differently between travis-ci and my computer. Unfortunately, on my pc I have no this warnings. So it complicates investigation a lot.

On ~5minute point (~610 samples) master consumed 490MB and patched 390MB, therefore it is not direct memory consumption, unfortunately.

@funny-falcon that's very strange.

@funny-falcon Do you think it would make a sense to try with latest Crystal release? It's been a while, maybe the issue disappeared? :)

Yes, I will try

Yeah i'm quite sad this PR stalled, Hash is one of the most-used datastructures in the compiler and many other crystal programs. And it's probably the datastructure with most scope for performance changes in it's implementation. I'd love to see crystal have a well-optimized Hash, and see what performance effects it has, especially if it has any effect on compile times.

With #8017 merged in should this one be closed?

Yes, closing.