[erlang-questions] divrem eep?

Tony Rogvall tony@REDACTED
Thu Aug 21 22:34:04 CEST 2014 

On 21 aug 2014, at 15:18, Björn-Egil Dahlberg <egil@REDACTED> wrote:

> On 2014-08-21 13:36, Tony Rogvall wrote:
>> 
>> On 21 aug 2014, at 12:34, Björn-Egil Dahlberg <egil@REDACTED> wrote:
>> 
>>> On 2014-08-21 12:11, Tony Rogvall wrote:
>>>> May I suggest a two stage commit, in the good old OTP way?
>>>> 
>>>> - First step is to implement a fairly simple bif that call the functionality I really want to get
>>>> (the remainder when doing bignum div calculations.) 
>>>> 
>>>> This includes  the work of checking special considerations with GC. It works now, but
>>>> needs more testing. As an example, I needed to blank the memory between the quotient 
>>>> and the remainder in the case when both quotient and reminder where both bignums.
>>>> (It should not really be needed, but I think the debug compiled emulator/gc expect everything to be super clean?)
>>>> 
>>>> - Seconds step is to use the previous work and implement an instruction that can be
>>>> used instead of call erlang:divrem when possible. This instruction needs a couple of 
>>>> variants I guess: One that return a tuple and one that store remainder in
>>>> a X register as instructed by compiler.
>>>> 
>>>> What about that ? 
>>> 
>>> Please, not an additional BIF. 
>>> 
>> Why not? What is the problem ?
> 
> My issue is that we are already littering erts with BIFs and several of them are probably unnecessary.
> 
After looking around a bit I found the following languages having a divrem / divmod build in function / operator!

Haskell: quoteRem, divMod
Python: divmod
Ruby: divmod
Visual Basic: DivRem
C#: DivRem
C++: DivRem
JScript: DivRem
C: div / ldiv

So why don't we ? 

>> 
>>> Do an optimization pass in beam-assembler to rewrite the two gc-bif-instructions to a single divrem instruction. Or better, yet .. just reorder them so you can please the loader and rewrite it in the load-step. No need for an additional assembly instruction in the compiler, just a specific instruction in the beam which is optimized with a load trick.
>>> 
>> I think one boring thing with this is that I need then to be dependent on that the compiler is smart enough to figure
>> this out (even if I have to implement it my self ;-)
>> How can a user be sure that the compiler really this optimisation? I think at least Björn G used to have 
>> thought about having to smart compilers ?
> 
> I think compilers should be smart and Erlangs compiler should be smarter than it is today. I don't know why you say Björn G. is against smart compilers. I don't presume to speak for him but he has implemented optimization passes for bitsyntax and ref-sends for instance, and that is kind of smart don't you think?
> 
> There are of course several way one might implement a divrem optimization. And it is an optimization and should thusly be treated as such.
> 
> Let's assume we implement an erlang:divrem/2 BIF which returns a two-tuple.
> A late pass in core erlang should recognize erlang:divrem/2 and translate it to a primop with two return values.
> In addition to that pass you may also have an earlier pass that recognizes the div rem operators and translate them to a divrem BIF so old code can benefit from this without rewriting the code.
> 
> The primop will be translated to a multiple Dst beam assembly code in v3_codegen .. and the loader just make a normal instruction for it.
> 
> The BIF will never enter into the equation unless you do apply .. but you could implement divrem(A,B) -> {A div B, A rem B}. in the erlang module and the optimizer would take care of it for you. You will of course build the tuple in that case.

A lot of arguments just to avoid a tiny BIF ! :-)

I think that return values from exported functions may present a small problem as well ?

-module(foo).
-export([kaka/2]).

kaka(A, B) ->
	erlang:divrem(A, B).

> 
> This whole thing reduces the divrem BIF to a placeholder, you still need the functionality of course but it will be implemented solely in the instruction. In other words, the BIF is unnecessary, just do it in the compiler and implement it as an instruction.
> 
> Furthermore, do away with the placeholder BIF and the pass to rewrite the divrem to a primop. Instead, recognize the occurrences of div rem operators and replace *them* with the primop instead.
> 
> If you fear the optimization will not take, just do erlc +S and look for it .. just like for any other compiler.
> 
Unless you have a language among the list above.

> But you know all this .. you are just yanking my chain =)
> 

Yes. :-)

> I say yes to a divrem optimization, it will probably help a few libraries. We have a couple in OTP that would surely benefit from it.
> I say no to a BIF since it is completely unnecessary .. especially since it is an optimization.
> 

I would like it both ways. That way I and other developers know what they get when they call divrem,
in all other cases the compiler may sometimes (when sunny) optimise div and rem,  to exectue a bit faster.


> // Björn-Egil
>> 
>> /Tony
>> 
>> 
>>>> 
>>>> :-)
>>>> 
>>>> /Tony
>>>> 
>>>> 
>>>> On 20 aug 2014, at 20:04, Björn-Egil Dahlberg <wallentin.dahlberg@REDACTED> wrote:
>>>> 
>>>>> It should probably be an instruction instead. 
>>>>> 
>>>>> The compiler should recognize if div and rem is used and combine them to one instruction. You have no issue with multiple return values if you do it in core for instance. I did some doodling with this on my previous summer vacation .. along with sub-expr-elim .. I stopped after the doodling phase =)
>>>>> 
>>>>> No eep necessary if you do it as an optimization pass, only light-eep.
>>>>> 
>>>>> // Björn-Egil
>>>>> 
>>>>> 
>>>>> 2014-08-20 19:41 GMT+02:00 Tony Rogvall <tony@REDACTED>:
>>>>> Hi list.
>>>>> 
>>>>> I have been playing with a new BIF called divrem today. Calling erlang:divrem(A,B) has the the same result
>>>>> as calling {A div B, A rem B}. (possibly with some strange exceptional cases that remain to be found :-)
>>>>> 
>>>>> Since the bignum div operation has always calculated the remainder as a "waste product" I thought it was
>>>>> about time to pick it up and make use if it.
>>>>> 
>>>>> The speedup when comparing calculation of {Q,R} = erlang:divrem(A,B) and Q=A div B, R=A rem B,
>>>>> is about 70-80% already around 60 bit arguments (64bit platform) (max speedup is of course 100%), 
>>>>> currently the downside is that divrem for small numbers are a bit slower, since a tuple {Q,R} is constructed 
>>>>> and the emulator have instructions for div and rem.
>>>>> 
>>>>> The above could probably be handle by regarding divrem as a builtin function with a multiple return value
>>>>> and have the compiler to generate an instruction for some instances of divrem.
>>>>> 
>>>>> I remember some work for handling multiple return values?
>>>>> 
>>>>> What about it ? eep?
>>>>> 
>>>>> /Tony
>>>>> 
>>>>> 
>>>>> _______________________________________________
>>>>> erlang-questions mailing list
>>>>> erlang-questions@REDACTED
>>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>> 
>>>>> 
>>>> 
>>>> "Installing applications can lead to corruption over time. Applications gradually write over each other's libraries, partial upgrades occur, user and system errors happen, and minute changes may be unnoticeable and difficult to fix"
>>>> 
>>>> 
>>>> 
>>>> 
>>>> 
>>>> _______________________________________________
>>>> erlang-questions mailing list
>>>> erlang-questions@REDACTED
>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>> 
>>> _______________________________________________
>>> erlang-questions mailing list
>>> erlang-questions@REDACTED
>>> http://erlang.org/mailman/listinfo/erlang-questions
>> 
>> "Installing applications can lead to corruption over time. Applications gradually write over each other's libraries, partial upgrades occur, user and system errors happen, and minute changes may be unnoticeable and difficult to fix"
>> 
>> 
>> 
> 

"Installing applications can lead to corruption over time. Applications gradually write over each other's libraries, partial upgrades occur, user and system errors happen, and minute changes may be unnoticeable and difficult to fix"



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20140821/137ebbe9/attachment.htm>

More information about the erlang-questions mailing list