Optimize Erlang comparisons or expose erlang:compare/2

Erlang/OTP Proposals Proposals: Ideas
1

I would like to propose exposing erts_cmp as erlang:compare/1.

In Erlang/Elixir, there are several data structures that rely on order, such as gb_trees, ordsets, and Elixir’s upcoming data structure for the type system.

Today, those data structures rely on comparisons:

insert_1(Key, Value, {Key1, V, Smaller, Bigger}, S) when Key < Key1 -> 
  ...
insert_1(Key, Value, {Key1, V, Smaller, Bigger}, S) when Key > Key1 -> 
  ...
insert_1(Key, Value, nil, _S) ->
  ...

The issue is that if you have a nested data structure where the difference between the keys are on the leaves, you are doing a lot of repeated work across those three branches (especially if they are equal).

My understanding, from looking at the generated .S files for a simple program, is that those are not optimised today, at least not for the compiler. How feasible does the compiler team think it would be to optimise those automatically? If not possible, could we expose erlang:compare/2 (potentially returning eq, lt, gt)?

Thank you,

2 Likes
2

I note that Prolog, C#, Java, Groovy, OCaml, Perl, PHP, Ruby, and Haskell have built-in three-way comparison of some form.
And so does C++ now, see p0515r3.pdf for background.
It’s often written as the ‘spaceship operator’ lhs <=> rhs.
Standard ML doesn’t have a generic three-way comparison but it has building blocks like Int.compare, String.compare,
List.collate, Array.collate, so you can compose whatever you need.
If you use function syntax as you propose, there’s no syntactic change to Erlang, and it’s a useful addition.

3

I think just exposing erts_cmp as erlang:compare/2 is the most pragmatic solution, because it’s trivial compared to implementing a compiler optimization. Also, a function is far more flexible than an optimization and can be used in a much wider variety of cases.

However, I feel

insert_1(Key, Value, {Key1, V, Smaller, Bigger}, S) when Key < Key1 -> 
  ...
insert_1(Key, Value, {Key1, V, Smaller, Bigger}, S) when Key > Key1 -> 
  ...
insert_1(Key, Value, {Key1, V, Smaller, Bigger}, S) when Key =:= Key1 -> 
  ...

is more idiomatic than

insert_1(Key, Value, {Key1, V, Smaller, Bigger}, S) -> 
    case erlang:compare(Key, Key1) of
        lt ->
            ...;
        gt ->
            ...;
        eq ->
            ...;
    end.

simply because it reduces the level of nesting and the length of each function body.

Ideally, we should implement both erlang:compare/2 and a compiler optimization since that lends the most flexibility in terms of functionality and style.

Perhaps we should go ahead with erlang:compare/2 to start with, and an optimization later if possible?

2 Likes
4

I pinged John who said an optimization should be fairly accesible to implement, so I went ahead and opened up an issue focused on that: Add beam_ssa_opt pass to streamline comparisons · Issue #10264 · erlang/otp · GitHub

I agree optimization is better if doable. :slight_smile:

1 Like
5

This has been discussed before, here. It died out, though.

I disagree to the “better” part :sweat_smile: That is, I don’t have anything against optimization, but behind-the-curtains magic like this is by and large something nobody knows about. Slight modifications of the code can lead to it not happening, and nobody knows why.

Therefore, I would opt for having both. I also think that @nzok put it well in the linked thread by saying that compare is intention-revealing, while a chain of < == > clauses is less so.

4 Likes