push_element/2 - efficient sliding window

[Ulf Wiger (AL/EAB)]

With an evening's hindsight, I've modified my hack to 
the following:

Erlang (BEAM) emulator version 5.4.8 [source] [hipe]

Eshell V5.4.8  (abort with ^G)
1> erlang:lshift_element({a,b,c,d},1).
{b,c,d,1}
2> erlang:rshift_element({a,b,c,d},1).
{1,a,b,c}


This might be useful for:

- A trace collector which keeps a fixed number of 
  elements in a history window. This could be used to 
  provide better error messages when a process crashes
  (e.g. having a message trace enabled on selected processes,
   and reporting the last N messages if one of them crashes.)
  For this to be useful, the history window must be very efficient.

- A limited undo buffer. It's easy enough to do unlimited undo
  in Erlang: just save old state variables in a list, and 
  pop the previous state variable to undo. Keeping only e.g.
  20 previous states is more cumbersome and expensive.
  This could be fairly easily done using the above BIFs:

  undoable_action(Action, S, UndoBuf) ->
     S1 = Action(S),
     {S1, erlang:lshift_element(UndoBuf, S)}.

  undo(UndoBuf) ->
     {element(1, UndoBuf), 
      erlang:rshift_element(UndoBuf, undefined)}.

If undo(Buf) returns {undefined, _Buf1}, there is no previous
State.


BTW, timing a loop of 1000 shifts on a 200-tuple, these BIFs cost 
about 2-3 microsecs each.

/Uffe


> -----Original Message-----
> From: owner-erlang-questions@REDACTED
> [mailto:owner-erlang-questions@REDACTED]On Behalf Of Ulf Wiger
> (AL/EAB)
> Sent: den 10 augusti 2005 16:23
> To: erlang-questions@REDACTED
> Subject: push_element/2 - efficient sliding window
> 
> 
> 
> Inspired by Joel Reymont's trials trying to make an on-line 
> trading platform in erlang, and by the recent discussions 
> about trace data, I thought I'd try to invent a new BIF 
> (never tried that before...)
> 
> Since I have no authority to introduce BIFs in Erlang, 
> getting this accepted could be done by:
> (a) the OTP team finding it a good idea and just doing it
> (b) enough users finding it useful to generate popular demand.
> 
> 
> erlang:push_element(Tuple, Value) pushes value into position 
> 1 of Tuple, shifting the existing values one step to the 
> right. This can be used as a fixed-size sliding window which 
> costs the same as setelement/3 to update.
> 
> Eshell V5.4.8  (abort with ^G)
> 1> erlang:push_element({a,b,c},3).
> {3,a,b}
> 2> erlang:push_element(v(1),3).        
> {3,3,a}
> 3> erlang:push_element({a,b},3).      
> {3,a}
> 4> erlang:push_element({a},3).  
> {3}
> 5> erlang:push_element({},3). 
> 
> =ERROR REPORT==== 10-Aug-2005::16:10:49 ===
> Error in process <0.30.0> with exit value: 
> {badarg,[{erlang,push_element,[{},3]},{erl_eval,do_apply,5},{s
> hell,exprs,6},{shell,eval_loop,3}]}
> 
> ** exited: {badarg,[{erlang,push_element,[{},3]},
>                     {erl_eval,do_apply,5},
>                     {shell,exprs,6},
>                     {shell,eval_loop,3}]} **
> 6> T = erlang:make_tuple(200,a). 
> {a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a|...}
> 7> timer:tc(erlang,push_element,[T,1]).
> {8,{1,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a|...}}
> 
> 
> My heavy-handed attempt at writing this in C (copy-paste 
> setelement_3 and tweaking it some):
> 
> BIF_RETTYPE push_element_2(BIF_ALIST_2)
> {
>     Eterm* ptr;
>     Eterm* hp;
>     Eterm* resp;
>     Uint size;
> 
>     if (is_not_tuple(BIF_ARG_1)) {
>     error:
> 	BIF_ERROR(BIF_P, BADARG);
>     }
>     ptr = tuple_val(BIF_ARG_1);
>     size = arityval(*ptr) + 1;   /* include arity */
>     if (size < 2) {
> 	goto error;
>     }
> 
>     hp = HAlloc(BIF_P, size);
> 
>     /* copy the tuple */
>     resp = hp;
>     *hp++ = *ptr++;
>     *hp++ = BIF_ARG_2;
>     size = size-2;
>     while (size--) {	/* XXX use memcpy? */
> 	*hp++ = *ptr++;
>     }
>     BIF_RET(make_tuple(resp));
> }
> 
> 
> You then have to go into erts/emulator/beam/bif.tab and add 
> the new BIF.
> In order to test it, make clean, and then 'make opt' (rebuild 
> the optimized beam).
> 
> 
> /Uffe
>