Why such performance difference?

Help & Support
1

I assume this is an issue between one using heap mem and other done on stack, but why such big performance difference? Code is twice as slow using [x, y].min vs {x, y}.min.

See: https://rosettacode.org/wiki/Hamming_numbers#Crystal

h << [x2, [x3, x5].min].min  # much slower
h << {x2, {x3, x5}.min}.min  # faster
h << (x3 < x5 ? (x2 < x3 ? x2 : x3) : (x2 < x5 ? x2 : x5))  # fastest
1 Like
2

Correct. [x, y] needs to allocate memory for the array, while {x, y} is a tuple which doesn’t need to allocate any memory on the heap as it uses stack memory which is much cheaper. Because of this, the order makes sense sense. The first has to allocate memory for two arrays AND iterate those arrays twice (because of #min). The second, doesn’t have to allocate any memory, but still has to iterate the values. The last one doesn’t have to allocate any memory, nor do any iterating.

Reference: Performance - Crystal

2 Likes
3

Thanks for the detailed quick response.

People coming from Ruby, which only has the [x, y].min/max syntax, will be unknowingly making their code slower by not understanding this. Having done enough Crystal now I was aware enough to compare the differences.

Have you considered a min/max function/method that just works on values and not containers like arrays/tuples? Something like min/max(x, y), for just such cases as in this example?

4

This applies to a lot of things since they are different languages.

These already exist as Math.max and Math.min.

2 Likes
5

OK. Good.

Addition:
Interestingly Ruby doesn’t have Math.min|max and I didn’t even notice it. I’m so used to just doing [x, y].min|max by reflex it never crossed my mind to check.

6

An additional reason is that {x, y}.min is a lot less opaque to LLVM’s optimizer. In the array version it’ll always need to generically handle it after fetching the values from memory in a loop. In the tuple version it can do many more optimizations based on the argument types, whether the values are constant etc. For example {1, 2}.max will very likely be just a literal 2 in the optimized code.

2 Likes
7

Maybe somebody could add to the crystal doc for Array#min etc. to warn people… :)

1 Like