Why cannot "last" be fast on vector?

[Warren Lynn]

This is an off-shoot subject from my last post "General subsequence function".

I found people had similar questions before (one year ago):
http://groups.google.com/group/clojure/browse_thread/thread/712711f049507c63/aea7cf438aa22922

As of Clojure 1.4, seems nothing changed, as "source" show here:

user> (source last)
(def
 ^{:arglists '([coll])
   :doc "Return the last item in coll, in linear time"
   :added "1.0"
   :static true}
 last (fn ^:static last [s]
        (if (next s)
          (recur (next s))
          (first s))))

Any reason for that? Thanks.

[David Nolen]

Don't hold your breath. Assume that the language was designed after much consideration. last is a sequence operation, not a collection operation. If the distinction doesn't make sense, I suggest you explore the design decision by writing some non-trivial Clojure code so you can arrive at your own satisfying answer why this was done. Otherwise you'll just listen to people repeat the same answer without hearing what is being said.

David 

[Tamreen Khan]

Here's a somewhat old but still generally useful article on how Clojure vectors are implemented:  http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ 

Vectors are optimized for random access, whereas lists are optimized for going through from the beginning to the end, which is exactly what the last function does.

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[Mark Engelberg]

On Thu, Jun 28, 2012 at 6:59 PM, Tamreen Khan <hist...@gmail.com> wrote:

Here's a somewhat old but still generally useful article on how Clojure vectors are implemented:  http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ 

Vectors are optimized for random access, whereas lists are optimized for going through from the beginning to the end, which is exactly what the last function does.

This doesn't really address the underlying question.

nth is a good example of a function that is fast for vectors, strings, and arrays, and only for lists uses the slower sequential implementation.

There's no technical reason that last couldn't do the same, dispatching on the underlying type to have a more efficient implementation for data types that support it.

The real reason is this: With the glaring exception of nth, Clojure tends to eschew functions with a fast path and a slow path, because programmers shouldn't have to do deep semantic analysis of their code to figure out which will get chosen.  In this case, however, we're talking about a function that is currently always slow.  Surely it would be a win to make it have a faster path in a large number of cases, right?  Well, the argument against that is eventually people would start to rely on it being fast for so many collection types, and then get burned when somehow their collection accidentally gets turned into a seq before last is called on it.  The theory is that it's better to force people to use a different function call, namely peek, to retrieve the last element quickly from a vector.

Honestly though, despite David Nolen's claim that this design decision will be obvious if you've coded enough Clojure, I've been programming in it for around 3-1/2 years, and I think the argument behind this design decision is a relatively weak one, so you are not making an unreasonable request.  In fact, the more I code in Clojure, the more I see that there are a number of core functions that require significant semantic analysis of the surrounding context to know how they will behave.  Either Clojure trusts that programmers can make determinations about the types of their collections or it doesn't.  Which is it?  Well, I'd argue there's a large body of evidence that under Clojure's current design, it's clear that you better know what you're doing.  If that's the case, why not go ahead and make last fast when it can be fast? 

Nevertheless, I hope I've clarified the reasoning behind the current design.  Early Clojure design decisions have a lot of inertia, so as David pointed out, this is very unlikely to change.

[Timothy Baldridge]

> Nevertheless, I hope I've clarified the reasoning behind the current
> design.  Early Clojure design decisions have a lot of inertia, so as David
> pointed out, this is very unlikely to change.

Well put.

I would argue as well, that many functional languages I've come across
take this stance: the language is opensource, you have namespaces, so
feel free to make a namespace called mycore, that includes all you
special versions of functions that you need, and then use that library
for your projects. It doesn't take very long to define these special
case functions and if they work for you, then just use them. For
instance, one such function I wrote tonight is called every-other
(returns '(1 3 5) if you hand it (1 2 3 4 5))

Does this function exist in clojure.core...not that I saw off-hand.
Does it really matter though? Not really. I'll copy and paste these
functions when I need them and go happily on my way. One of the
biggest strengths of functional programming is that we can build up
snippets of functions like this, and when we use then in our programs
we can't tell that they weren't included by default.

As Gerald Sussman said at the last Strange Loop conference: be a
Libertarian when it comes to programming. Don't restrict others to
your view of programming, liberty to you and to me and to everyone.
You can code in your style, I'll code in mine, and Clojure (or Lisp in
the case of the quote), shouldn't constrain me to its view of the
world.

Timothy

[David Nolen]

So you recommend that "last" should be only function that accepts IPersistentStack *and* ISeqable and does the appopiate thing? Or are there others?

--

[Meikel Brandmeyer (kotarak)]

Hi,

Am Freitag, 29. Juni 2012 05:26:07 UTC+2 schrieb tbc++:

For instance, one such function I wrote tonight is called every-other
(returns '(1 3 5) if you hand it (1 2 3 4 5))

user=> (take-nth 2 [1 2 3 4 5])
(1 3 5)

Kind regards
Meikel
 

[Warren Lynn]

Tamreen:

Thank you. Your posts really explained why it is so. I understand the reasons now, but I can hardly agree those reasons are good ones (not arguing with you, as you pointed out, the reasons are weak for this case).

As I pointed out before in my other post ("General subsequence function"), mixing abstraction with speed path is really a bad idea, and might be a classical example of what Rich called "complecting". In practice, it did not achieve what it tries to achieve either (one of the big complaints I read from the Web about Clojure is it is really hard to know the speed performance). For speed, the classical solution is:

1. Put good documentations on the functions, and the programmer needs to have some idea what data structure is fast/slow for what use. If the programmer does not have a clue, why would making "last" artificially slow on vectors help? Plus, whether one data structure is slower than the other for certain operations can also be an implementation detail that may change.
2. Use a profiler, so you can keep optimizing on the current hot spots.

The above solution has no interference with abstraction.

[David Nolen]

On Fri, Jun 29, 2012 at 10:51 AM, Warren Lynn <wrn....@gmail.com> wrote:
> 1. Put good documentations on the functions, and the programmer needs to
> have some idea what data structure is fast/slow for what use. If the
> programmer does not have a clue, why would making "last" artificially slow
> on vectors help? Plus, whether one data structure is slower than the other
> for certain operations can also be an implementation detail that may change.

The design choice has nothing to do with speed, it has nothing to do
with concrete types like lists and vectors either, no matter what
might have been said before by others.

David

[Warren Lynn]

Sorry, I should have addressed my last post to "puzzler".

[Warren Lynn]

Surely nobody can restrict/enforce anything on anybody, and I can always have my own "mycore" ns. In theory, I could even create my own language without the need to persuade anybody (or just fork from Clojure and have my own private copy). That will be the ultimate "Libertarian", but some people (including myself) may call me "savage" in doing so, unless you can attract enough people to form a new society around you, like Rich has done. :-)

[Warren Lynn]

The design choice has nothing to do with speed, it has nothing to do
with concrete types like lists and vectors either, no matter what
might have been said before by others.

David

If the design choice has nothing to do with speed path, Could you let us know why we cannot get free speed improvements on vectors?
 

[David Nolen]

On Fri, Jun 29, 2012 at 12:13 PM, Warren Lynn <wrn....@gmail.com> wrote:
> If the design choice has nothing to do with speed path, Could you let us
> know why we cannot get free speed improvements on vectors?

I already have.

[Weber, Martin S]

I'm sorry to say, but IMHO you failed to communicate the critical point to
your audience. If your audience keeps failing to grasp the point, and
communicates this failure back by asking the same question..

I do understand the distinction between a collection and a sequence and
something being a collection or a sequence operation. That doesn't stop
certain sequences from being capable of doing certain things in a better
way. I simply do not understand the reason of clojure/rich/whoever
throwing away a potential performance increase because "this operation
does not operate on the correct level to be performant. If you expect this
to be performant, rewrite it on a lower level." That stance seems
surprisingly patronizing.

Also, it seems of course clojure itself is inconsistent with regard to
that design choice. At least looking at Timothy Baldridge's reply to
"possible bug in reducer code" makes me think so. I mean come on, a high
level operation being optimized on certain types? Heresy!

Regards,
-Martin

[David Nolen]

On Fri, Jun 29, 2012 at 12:30 PM, Weber, Martin S <martin...@nist.gov> wrote:
> I'm sorry to say, but IMHO you failed to communicate the critical point to
> your audience. If your audience keeps failing to grasp the point, and
> communicates this failure back by asking the same question..

Perhaps we differ on the matter of audience participation? :)

The functions found in the standard library fall out of Clojure's well
considered protocol / interface partitions. Don't take my word for it
as I already said - examine the protocol / interface partitions
yourself.

In the end you'll be left with a discussion about *names* (peek vs.
last) - not performance, concrete types or anything else. At which
point we'll probably agree that it's water under the bridge and it's
not going to change.

David

[Nicolas]

I would say we can have different ways of designing things.

A way is to design abstractions and provide services on top on theses
abstractions. The abstraction here is ISeq. That is sequences. Last
is not part of the ISeq abstraction and just work on top of it. There
is no way to access last element directly from something that is just
a an ISeq. So last can't use it.

If last was part of ISeq abstraction, you would not need a separate
last function at all. But this would also mean that all ISeq
implementations would need to implement last. This would be sure
conveniant, but this is not the same abstraction. It is also heavier
(more code, more maintenance...). And for some implementation like
networks streams, this would be anoying than anything as it would
provide no added value.

Seq abstraction is exactly that: a very basic (yet powerfull)
abstraction for accessing streams, linked list and other specialized
structures that are sequential in essence.

Clojure team could have designed last to work on any possible type
where it make sense and so have better performance for each possible
type. An efficient implementation would use a protocol to do so.
Making last its own abstraction. This is indeed possible, but was not
the choice here.

Fact is others abstractions already allow you to have the last element
directly like Indexed if this important to you.

So yes we could have a better last, promoting it to a full
abstraction. Like clojure could be many more things. Is this REALLY a
priority for the future of clojure? Not at least for clojure core
team. I tend to share their views. You have the right to disagree.

On my side, I'am far more interrested to see progress in
clojurescript, IDEs, tooling, maybe even grid computing.

You care about last. This is your right... And well why not implement
your own last in contrib or private lib and use if it is important?
Like other members of the community implemented code matching their
own interrest.

It is logical you ask for it, but there is no need to insist or maybe
be a little offensive if others don't share your views.

Regards,

Nicolas Bousquet.

On 29 juin, 01:32, Warren Lynn <wrn.l...@gmail.com> wrote:
> This is an off-shoot subject from my last post "General subsequence
> function".
>

> I found people had similar questions before (one year ago):http://groups.google.com/group/clojure/browse_thread/thread/712711f04...

[Sean Corfield]

On Fri, Jun 29, 2012 at 7:51 AM, Warren Lynn <wrn....@gmail.com> wrote:
> 1. Put good documentations on the functions, and the programmer needs to
> have some idea what data structure is fast/slow for what use.

At the risk of continuing what is quickly becoming a rather fruitless
thread, I figured I'd quote the docstrings from last and peek:

last: Return the last item in coll, in linear time

peek: For a list or queue, same as first, for a vector, same as, but
much more efficient than, last. If the collection is empty, returns
nil.

That seems like pretty good documentation to me. (last my-vector) is
documented to be a linear operation. (peek my-vector) is documented to
be "much more efficient". last is not dependent on the type of its
argument, peek is.
--
Sean A Corfield -- (904) 302-SEAN
An Architect's View -- http://corfield.org/
World Singles, LLC. -- http://worldsingles.com/

"Perfection is the enemy of the good."
-- Gustave Flaubert, French realist novelist (1821-1880)

[Warren Lynn]

Thanks for clarifying more on the rationale behind the design. Also a note on the tone: I never thought insisting on a view is offensive. Insisting our views are the essence of a debate. But we need to insist based on reasons and acknowledge when we are wrong. Also, I realize that sometimes debating on a forum is different from face-to-face debating and offense is easier to make. I hope nobody took any offense.

Here actually I am not only trying to ask for a faster "last". I am trying to understand some of the designs here (and along the way insisting on my own "right" one), because I have this regretful feeling that Clojure has some really nice LISP features but failed on some basic stuff, and I am seriously doubting whether I should invest more on it (possibly on a production system). I will be more than glad to be convinced that the design is sound, but I will need enlightenment.

My understanding here is "ISeq" is an INTERNAL, implementation level interface/abstraction, not the user/language level abstraction (which in this case should be "ordered collection", as somebody called), so whether "last" is part of "ISeq" is irrelevant. In my view, at the user/language level, last should work on all ordered collections as fast as it can without EXPOSING whatever internal implementation is on.

I know there is a lot of exciting projects going on with Clojure. But a good review of the design does not conflict with that, and may be beneficial for future exciting projects.

I am still insisting on my view, but I hope its based on reasons.

[Warren Lynn]

Even not a single action is taken because of this thread, I still would not consider the thread fruitless. It helped me (and maybe others) understand the issue better.

My point was: you need a clear documentation on a coherent, consistent abstraction, and let the programmer to understand. Just clear documentation is not enough. You can document a very messy system in clear documentation (maybe the US tax code?).

Here, we are having both "peek" and "last", which is not coherent to me. consider the documentation on an alternative design:

last: get the last element from an ordered collection. for queues and linked lists, it takes linear time. for vectors, it takes constant time.

and get rid of "peek" (we already have "first" for linked list and queues, right?)

Which one is cleaner?

[David Nolen]

On Fri, Jun 29, 2012 at 4:25 PM, Warren Lynn <wrn....@gmail.com> wrote:
> My understanding here is "ISeq" is an INTERNAL, implementation level
> interface/abstraction, not the user/language level abstraction (which in
> this case should be "ordered collection", as somebody called)

It is not internal. It is a user/language level abstraction.

David

[Warren Lynn]

You are right, clojure.lang.ISeq is public and I can see it from "user" namespace.

But that is not what I meant, the "ordered collection" is a language level abstraction, clojure.lang.ISeq is an exposed interface. With regard to "last", clojure.lang.ISeq is still implementation level, even if it is exposed.

In other words, the "ordered collection" abstraction is like (or maybe the same as) the "clojure.lang.Seqable". And vectors belongs to it:
(isa? clojure.lang.PersistentVector clojure.lang.Seqable) => true

[Mark Engelberg]

It is clear that some collections *could* support a more efficient last.  Anything with random access.  Anything that supports rseq (e.g., sorted collections). 

There are multiple ways to accomplish this; I presume a protocol would do the trick.

Perhaps the original design decision is easily justified in terms of the original way the collections were factored into various interfaces, but now that it is so easy to make functions polymorphic over different types via protocols, I can't imagine this would be a difficult change if anyone cared to do it.

I don't think anyone is arguing that the current semantics aren't well documented; the claim is that it violates the "Principle of Least Surprise" in the sense that most people expect a built-in core function to be implemented efficiently for the cases when it can be implemented efficiently.  Everyone knows that a vector, for example, is designed to provide very fast access to the last element, so it is counterintuitive that a function called "last" ignores this capability and just treats vector as a generic sequence, searching through the items one-by-one to get to the last element.

BTW, I disagree with Warren's comment about how a better last would eliminate the need for peek.  Even if you have last, peek is a very useful way of guaranteeing consistent stack semantics for a wide variety of collection types.

[Warren Lynn]

Although I have not yet looked at any of Clojure's internals yet, I suspect the change won't be too difficult (for the right person). So I hope/wish someone with enough knowledge, skills and influence will agree with me and advocate a review of the design ("last" may not be the only one with issues) and fix some of those things before things get too messy down the road.

Looking "peek" from your point of view (actually from another abstraction point of view), it seems useful. Thank you.

[David Nolen]

On Fri, Jun 29, 2012 at 5:17 PM, Mark Engelberg
<mark.en...@gmail.com> wrote:
> It is clear that some collections *could* support a more efficient last.
> Anything with random access.  Anything that supports rseq (e.g., sorted
> collections).

And what does overloading last in this way mean for drop-last,
take-last, but-last? All sequence functions.

David

[Warren Lynn]

The same? If internally it can be faster, be faster. If not, don't change.

[Sam Ritchie]

Perhaps place them inside a protocol, where core supplies implementations for ISeq only? This would make it easier to extend efficient behavior to other types without placing a big burden on core.

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

--

Sam Ritchie, Twitter Inc

703.662.1337

@sritchie09

(Too brief? Here's why! http://emailcharter.org)

[David Nolen]

On Fri, Jun 29, 2012 at 6:49 PM, Warren Lynn <wrn....@gmail.com> wrote:
> The same? If internally it can be faster, be faster. If not, don't change.

For which types do you think they can be made faster?

David

[David Nolen]

On Fri, Jun 29, 2012 at 7:28 PM, Sam Ritchie <sritc...@gmail.com> wrote:
> Perhaps place them inside a protocol, where core supplies implementations
> for ISeq only? This would make it easier to extend efficient behavior to
> other types without placing a big burden on core.

ISeq *is* an interface on Clojure JVM. But ideally it would be
protocol as in ClojureScript. But then all ISeq implementing types
must also implement this new protocol you are suggesting to get these
basic *generic* sequence operations we enjoy today.

David

[Mark Engelberg]

vectors and sorted collections, for sure.

[Warren Lynn]

I really don't know, as I know very little about how these things are implemented. My point is, we maintain a coherent abstraction and get the best speed we can. To recap, what I don't like about current "last" is it makes writing generic code difficult. Currently, I need to use "peek" for vector and "last" for sequence. That defeats the very purpose of abstraction.

[Mark Engelberg]

I think the suggestion is to create a protocol for each function that could potentially gain speed improvements for specialized types.  So for example, ILast could be a protocol.  extend ILast to have an implementation for ISeq (using the current code).  Then, there's no burden on implementers of new data types that implement ISeq to do any additional work, but those who want to create custom implementations of last for other data types are free to do so.  Win-win.

[Warren Lynn]

Again, I don't know the internal details. If you are saying because of the current implementation, the change is difficult, then we will be talking about the implementation, not about the abstraction design. I have very little to say about that.

[David Nolen]

On Fri, Jun 29, 2012 at 8:02 PM, Mark Engelberg
<mark.en...@gmail.com> wrote:
> I think the suggestion is to create a protocol for each function that could
> potentially gain speed improvements for specialized types.  So for example,
> ILast could be a protocol.  extend ILast to have an implementation for ISeq
> (using the current code).

As I said, if ISeq and ILast are both protocols that won't work. No
protocol inheritance.

At this point I think some of the basic challenges are clear. Would
love to see someone actually build these ideas out purely on top of
protocols instead of making this thread any longer.

A good Clojure implementation via ClojureScript would make the
arguments more convincing ;)

David

[Bobby Eickhoff]

Warren, you're on the right track with your alternative design: Intuitively and ideally, "last" should return the last element of a finite, ordered collection.  But Clojure's "last" operates on sequences, not collections.  This is problematic because sequences can be (effectively) infinite.  Calling "last" on an arbitrary sequence is, therefore, dubious at best.  It's what Doug Crockford might call an attractive nuisance: sometimes useful, but dangerous.  So "last" isn't a function I would spend alot of time trying to fix.

There is historical precedent for Clojure's "last" function.  For example, see Haskell's "last" function in Data.List.  Historical precedent doesn't justify the design, but it helps explain how we got here.

Bobby

[Mark Engelberg]

On Fri, Jun 29, 2012 at 5:17 PM, David Nolen <dnolen...@gmail.com> wrote:

As I said, if ISeq and ILast are both protocols that won't work. No
protocol inheritance.

I don't see how inheritance factors into this.  This works just fine in Clojure 1.3.  What am I missing?:

(defprotocol Last
  (better-last [s]))

(extend-protocol Last
  nil
  (better-last [s] (last s))
  Object
  (better-last [s] (last s))
  clojure.lang.ISeq
  (better-last [s] (last s))
  clojure.lang.Reversible
  (better-last [s] (first (rseq s)))
  java.lang.String
  (better-last [s] (nth s (dec (count s))))
  clojure.lang.IPersistentVector
  (better-last [s] (peek s)))

[Warren Lynn]

Bobby:

Thanks for confirming my sanity here. But I have a different opinion on the "attractive nuisance" label on "last" function. Sure if you call "last" on an infinite sequence that will not work (the program will get stuck?), but it is no more dangerous than other dynamic part of the language. Think about a higher order function, a function that takes another function as an argument, isn't that much more dangerous? I mean, you don't even know what kind of function people may throw into it, and the damage could be bigger (for example, it may even wipe out you hard drive). As a dynamic language gives high level of freedom and abstraction power, the programmer needs to take certain responsibilities too, because the compiler will catch much less errors than a statically typed language.

So I still think "last" is a very useful function and worth fixing. Ideally, if a sequence can be checked if it is infinite or not so "last" can throw an exception when not applicable, but that may not be feasible with lazy sequences. And again I feel the responsibility should be more on the programmer's side.

[David Nolen]

ISeq is a interface on Clojure JVM. So that will work. In ClojureScript it won't as ISeq is a protocol.

--

[Mark Engelberg]

On Fri, Jun 29, 2012 at 4:50 PM, David Nolen <dnolen...@gmail.com> wrote:

ISeq *is* an interface on Clojure JVM. But ideally it would be
protocol as in ClojureScript. But then all ISeq implementing types
must also implement this new protocol you are suggesting to get these
basic *generic* sequence operations we enjoy today.

I see, you're not saying it can't be done in Clojure, you're saying it wouldn't work on ClojureScript.  It seems to me that's a limitation of either ClojureScript, or protocols, or both.  My guess is that it's a limitation of ClojureScript, because my understanding is that in Clojure, every protocol generates a Java interface, so I can't think of any reason why you couldn't list that generated interface as a "type" in another protocol (although I haven't tried it).

If that doesn't work, then this merits more discussion, I think, because it points to a real issue about building large systems with protocols.  The issue of "thin" vs "fat" interfaces is a tricky one in many languages, and one of the most reasonable solutions is to give the fat interface an implementation in terms of the thin one, so that implementers are only required to implement the thin interface, but can override the default implementation of the fat interface if need be.  If this can't be done in Clojure, it would be good to figure out an alternative that will work.