7 ms·

> some weird corner cases (like how `(first ..)` is slower than `(nth .. 0)` I would not consider this a corner case; it is stated in (first) docstring. (first

by dig1 5y ago

> some weird corner cases (like how `(first ..)` is slower than `(nth .. 0)` I would not consider this a corner case; it is stated in (first) docstring. (first) will create seq [1] object, then it will fetch the first element. (nth), on other hand, will not create seq object. > The STL is very strict on the "zero cost abstraction" front. Many edge cases which are lost in myriad of classes. For example, vector will allocate more memory than there are actually elements in it, and you never know when it will start resizing it (this is implementation detail). I would not call this as "zero cost abstraction". [1] https://clojuredocs.org/clojure.core/seq https://clojuredocs.org/clojure.core/seq

vnorilo 5y ago
I think zero cost in this context means compile-time polymorphism (templates) instead of runtime polymorphism (virtual functions).
geokon 5y ago
I mean, I didn't say it's undocumented behavior :) but when the default performance of a basic function like `first` is not O(1) then that strongly suggests that performance is secondary to composability/flexibility (I'm actually not clear why it doesn't alias to `(nth .. 0)` .. I'm sure there is a good reason) In Clojure you don't really reason about vector's run time behavior at all like in C++. You can't even ensure cache locality b/c different items can have any size. You can try to be clever and fall back to Java arrays, but the documentation says "It is recommended that you limit use of arrays to interop with Java libraries that require them as arguments or use them as return values." and the language doesn't provide the syntactic sugar for their easy use with the other data structures. So it kinda looks like the language is actively trying to discourage you from using an efficient data structure. My previous post was trying to say that maybe you could elevate arrays to be more first class, make `first` and company O(1), maybe lose some flexibility/composability in the process but find some performant middle ground between Clojure and C++. I have no idea if this is actually achievable. btw, STL vector resizing is a total non issue ... Most of the time you'd just allocate sufficient space beforehand (then it's truly zero cost). If you need to do something dynamic and care about when it resizes then you can just resize manually as you go (that's also zero cost - b/c this resizing is unavoidable and part of your algorithm). The default auto-resizing behavior just handles the resizing for you in a sane O(1) way
- didibus 5y ago
  > function like `first` is not O(1) The Clojure `first` function on lists and vectors is O(1), not sure why you think it isn't. Are you thinking of `last` ?
  - geokon 5y ago
    I wasn't exactly able to find it's complexity - but here is a blurb about it's performance issues: https://tech.redplanetlabs.com/2020/09/02/clojure-faster/#first-and-last https://tech.redplanetlabs.com/2020/09/02/clojure-faster/#fi... I think I'm may have been wrong and it's not a complexity issue, but just incredibly slow.
    - didibus 5y ago
      Well, "incredibly" is a weasel word. 0.05 nanosecond is fast enough for most general use case, you can consider that incredibly slow or fast I guess depending what you compare it against or what your use case is. The reason it is slower than `nth` is because `first` is a sequence function, so it first coerces the type into a sequence, and then it returns the first element of that sequence. The creation of the sequence object wrapping the vector is what slows it down compared to `nth`, but it is still O(1).
      - geokon 5y ago
        Yeah, I just tested it out and you're you're right, it doesn't depend on the size of the container. Sorry about that But the difference is more than 5x. That's kinda nuts.. In the context of C++ you don't just shrug your shoulders at 5x. There is a really long discussion on GoogleGroups about why this was designed this way.. and I'm not sure I entirely understood the rational so I'm wary to say anyone is wrong. I definitely want to give them the benefit of the doubt and say it's probably like that for a good reason. But people were surprisingly very dismissive of this being a problem. To me it looks kinda obviously ugly (and maybe that's a tradeoff worth making). Furthermore, you have `peek` for the tail position, but no equivalent for the first position? To me it looks strange.. I actually don't mind that Clojure doesn't emphasis performance. To me it's just part of the tradeoff. But if you point this out then passionate people come out of the woodworks and get really defensive about it :S

by dig1 5y ago

vnorilo 5y ago

I think zero cost in this context means compile-time polymorphism (templates) instead of runtime polymorphism (virtual functions).

geokon 5y ago

I mean, I didn't say it's undocumented behavior :) but when the default performance of a basic function like `first` is not O(1) then that strongly suggests that performance is secondary to composability/flexibility (I'm actually not clear why it doesn't alias to `(nth .. 0)` .. I'm sure there is a good reason) In Clojure you don't really reason about vector's run time behavior at all like in C++. You can't even ensure cache locality b/c different items can have any size. You can try to be clever and fall back to Java arrays, but the documentation says "It is recommended that you limit use of arrays to interop with Java libraries that require them as arguments or use them as return values." and the language doesn't provide the syntactic sugar for their easy use with the other data structures. So it kinda looks like the language is actively trying to discourage you from using an efficient data structure. My previous post was trying to say that maybe you could elevate arrays to be more first class, make `first` and company O(1), maybe lose some flexibility/composability in the process but find some performant middle ground between Clojure and C++. I have no idea if this is actually achievable. btw, STL vector resizing is a total non issue ... Most of the time you'd just allocate sufficient space beforehand (then it's truly zero cost). If you need to do something dynamic and care about when it resizes then you can just resize manually as you go (that's also zero cost - b/c this resizing is unavoidable and part of your algorithm). The default auto-resizing behavior just handles the resizing for you in a sane O(1) way

didibus 5y ago
> function like `first` is not O(1) The Clojure `first` function on lists and vectors is O(1), not sure why you think it isn't. Are you thinking of `last` ?
- geokon 5y ago
  I wasn't exactly able to find it's complexity - but here is a blurb about it's performance issues: https://tech.redplanetlabs.com/2020/09/02/clojure-faster/#first-and-last https://tech.redplanetlabs.com/2020/09/02/clojure-faster/#fi... I think I'm may have been wrong and it's not a complexity issue, but just incredibly slow.
  - didibus 5y ago
    Well, "incredibly" is a weasel word. 0.05 nanosecond is fast enough for most general use case, you can consider that incredibly slow or fast I guess depending what you compare it against or what your use case is. The reason it is slower than `nth` is because `first` is a sequence function, so it first coerces the type into a sequence, and then it returns the first element of that sequence. The creation of the sequence object wrapping the vector is what slows it down compared to `nth`, but it is still O(1).
    - geokon 5y ago
      Yeah, I just tested it out and you're you're right, it doesn't depend on the size of the container. Sorry about that But the difference is more than 5x. That's kinda nuts.. In the context of C++ you don't just shrug your shoulders at 5x. There is a really long discussion on GoogleGroups about why this was designed this way.. and I'm not sure I entirely understood the rational so I'm wary to say anyone is wrong. I definitely want to give them the benefit of the doubt and say it's probably like that for a good reason. But people were surprisingly very dismissive of this being a problem. To me it looks kinda obviously ugly (and maybe that's a tradeoff worth making). Furthermore, you have `peek` for the tail position, but no equivalent for the first position? To me it looks strange.. I actually don't mind that Clojure doesn't emphasis performance. To me it's just part of the tradeoff. But if you point this out then passionate people come out of the woodworks and get really defensive about it :S