push_element/2 - efficient sliding window

[Ulf Wiger (AL/EAB)]

Richard A. O'Keefe wrote:
> 
> With reference to (fixed size) sliding windows,
> I asked whether we really needed built-in support.
> 
> "Ulf Wiger" <ulf@REDACTED> replied:
> 	It's about as justified as erlang:make_tuple/2
> 	and erlang:append_element/2.
...

> 
>     erlang:append_element(Tuple, Element) ->
> 	list_to_tuple(tuple_to_list(Tuple) ++ [Element]).
> 
> Again, making this a built-in operation saves a constant factor in
> time, but it is *still* an O(N) operation and therefore best avoided.

Based on the current implementation of (large) tuples, it's an O(N)
operation. I think large tuples should be represented differently
than they are today, and then append_element/2 could be made cheaper
(not that that in itself would be the justification for changing the
representation - reducing the cost of setelement/3 is a much better 
reason.)



> Here is *one* operation which could handle them both:
> 
>     set_or_extend(Index, Tuple, New_Element, Fill)
> 	when tuple(Tuple), integer(Index), 1 =< Index, Index =< 
> size(Tuple)
> 	-> setelement(Index, Tuple, New_Element);
>     set_or_extend(Index, Tuple, New_Element, Fill)
> 	when tuple(Tuple), integer(Index), Index > size(Tuple)
> 	-> list_to_tuple(tuple_to_list(Tuple) ++
> 		lists:map(fun (N) -> if N < Index -> Fill
> 				      ; N = Index -> New_Element
> 				     end end,
> 		    lists:seq(size(Tuple)+1, Index))).
> 
> That is, if the index is outside the existing range, the tuple is
> extended with the Fill element, and then the resulting tuple has
> the element at Index replaced by New_Element.

Personally, I would prefer the BIF not to make assumptions about
whether or not an index out of range is a programming error or 
an implicit wish to extend the tuple. Having setelement/3 and 
extend_tuple/3 as separate BIFs allows the programmer to 
easily write set_or_extend/4 as a combination of the two, using
a trivial wrapper.



> My real point is simply that hacking oodles of special cases 
> is not the best way to design built-in functions; there are
> generalisations which should be exploted.

Agreed.



> In the same way, the proposed 'push' operation (which is, 
> contrary to the usual sense of 'push' in computing, also a
> truncate; such clashes are the snake's warning rattle that
> something bad is about to happen) is a quirky special case.

In part as a response to the snake's warning rattle, I made
a subsequent post where push_element/2 had been renamed as 
rshift_element/2, and complemented with lshift_element/2.
I don't claim to have found ideal names yet, or even the ideal
functions, but at least it's better than push_element/2.



> There must be some good generalisations waiting to be
> thought of.

Indeed, and a good enough reason to set the ball rolling 
with some provocatively named custom BIFs.  ;-)



> Let's push this one a little further.
> Can we find ONE operation which covers make_tuple/2, append_element/2,
> the proposed push_element, and a whole lot of other things, 
> which could
> reasonably go in C?
> 
> Yep.
...
> There has to be a better name than tuple_stuff/6, but I hope you get
> my point.  ONE built-in goes into erlang:, lots of special-purpose
> wrappers go in a new tuples: modules, and further special cases can
> be added without penalty.

I have no problem with that (except perhaps trying to write 
this function myself in C...)




> The obvious question has to be this:
>     if you want a sliding window, is a tuple the right tool 
> for the job?
> The equally obvious answer is "NO WAY!"  Why?  Because even 
> with a BIF,
> it's O(N) time and O(N) space turn-over to add an element (and remove
> another), whereas with the right kind of tree it can be done in O(lgN)
> time and O(lgN) space.  (Proof:  think of it as a priority queue.  At
> every step we remove the element with the smallest timestamp and add a
> new element with a greater timestamp than any existing element.)
> Using a tuple only makes sense for SMALL fixed windows.

Not necessarily. While discussing this with Joel, (1) a fairly common
size of the sliding window for a trading system would be 200, and 
many of the algorithms require random access to the elements of the 
window. Now, random access in a tuple is O(1) and *really* cheap.
It becomes a question of which one is the most frequent operation:
slide or read? If one can make it cheap enough to slide a tuple,
it certainly wins hands-down on read.

I made a comparison between using the lines module (which mimics an
array using a tuple tree) and creating a sliding window using 
a list and list_to_tuple()). It was cheaper to slide the tuple tree,
but no so much that it justified the overhead imposed by read().



> 	I see no reason why we should grace the list type with
> 	optimized versions of append, subtract, keymember, member,
> 	keysearch and reverse, but not offer similar optimizations
> 	for tuples.
> 
> I see no reason why the list type should be graced with 
> optimised versions
> of append, subtract, member, keymember, keysort, and reverse. 
>  At least, in an ideal world.

Yes, well, many of the BIFs would go away in that ideal world.
The reason for those BIFs is that their use is common enough 
that optimizing them tends to lead to significant cost savings
in real applications.


> The only reason for having BIF support for list operations is 
> a compiler that doesn't generate fast code for plain Erlang
> versions. With time, one may be permitted to HiPE that the
> need for such things will be reduced.

Personally, I couldn't care less whether a function is made
fast through compiler trickery or by making it a BIF. What 
does concern me is that some functions need to be made fast,
or people will be tempted to write un-intuitive code.

Tuples are great semantically, but people refrain from using
them sometimes because some things are difficult or expensive
to do. Is it a law of nature that large tuples should be expensive
to update?

Another example is the lack of GC for atoms, which causes people
to bend over backwards trying to solve problems that should be 
easy. Perhaps rather than the lack of atom GC, the real problem
is that you can't register processes, ports or ETS tables by 
anything that's not an atom.



> 	I think tuples could be used to great advantage
> 	in many cases where we use ETS today, if only a few steps
> 	were taken to ease their use a little bit.
> 	
> I think that's a good idea, *BUT* hacking one special case at a time
> may not be the best way to do that.

You're absolutely right. of course. However, hacking one special
case in order to get a discussion started may well be worth the
effort.



> 	Another thing I'd like to see for tuples is a syntax
> 	addition:
> 	
> 	tag_search([{Tag | _} = T|_], Tag) ->
> 	    {value, T};
> 
> Agreed.

Well, (:


/Uffe