5 ms·

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 tha

by 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
      - didibus 5y ago
        > I actually don't mind that Clojure doesn't emphasis performance I think this is the statement that people get defensive about. Clojure doesn't try to be the fastest language in the world, so beating Fortran is a non goal, hopefully that's obvious, but it takes performance very seriously, often at the detriment of usability in fact. Chunked sequence is one such example, it's purely done for performance reasons, but causes people a lot of headaches as it creates quite a few gotchas around lazy sequences. First is another example, but I agree this one depends on your own philosophy and Clojure has an unconventional philosophy here. The philosophy is that the choice of data-structure matters, and when performance is required, the programmer should make the right data-structure choices and use the appropriate data-structure optimized functions. You could say that goes even further, that really the choice of constructs and the design of how to implement something matters if your use case is performance sensitive, and so small performance improvements like first having a special case on vectors don't matter for performance sensitive use cases anyways. What that means is that, from my understanding, Clojure core devs aren't opposed to `first` and `last` having a faster path in some special cases, but they see that as an unimportant feature, that's way lower on the list of priorities, and they aren't convinced it's even worth the added complexity it would bring to the language implementation. Effectively, where some languages say, this abstraction is so cool, because you can swap out the collection for a different one and get a free speed boost, Clojure says: this abstraction is so cool, because there is no collection you can switch too that would make the performance degrade. So when it comes to performance trade offs, Clojure focuses on making the default and most straightforward way to implement something "fast enough" and scalable to larger inputs. You can think of this as for most use cases, the time it takes for a O(1) will be sufficient for the user, and your program won't choke if your input size grows larger. And in the more exceptional cases where the O(1) isn't fast enough, or you have ridiculously large inputs beyond what even the common "at scale" use cases are. Well for those, Clojure wants to quickly make you realize you should not try to use the default and most straightforward way to implement this, but instead you need to immediately design for that performance. And this isn't black or white either, there are cases where something was deemed worth having a faster internal implementation or special case, because it would have a substantial overall impact, for example with chunked sequence and transducers, or with how small maps are made into an array map, or with transients, etc.

by geokon 5y ago

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
    - didibus 5y ago
      > I actually don't mind that Clojure doesn't emphasis performance I think this is the statement that people get defensive about. Clojure doesn't try to be the fastest language in the world, so beating Fortran is a non goal, hopefully that's obvious, but it takes performance very seriously, often at the detriment of usability in fact. Chunked sequence is one such example, it's purely done for performance reasons, but causes people a lot of headaches as it creates quite a few gotchas around lazy sequences. First is another example, but I agree this one depends on your own philosophy and Clojure has an unconventional philosophy here. The philosophy is that the choice of data-structure matters, and when performance is required, the programmer should make the right data-structure choices and use the appropriate data-structure optimized functions. You could say that goes even further, that really the choice of constructs and the design of how to implement something matters if your use case is performance sensitive, and so small performance improvements like first having a special case on vectors don't matter for performance sensitive use cases anyways. What that means is that, from my understanding, Clojure core devs aren't opposed to `first` and `last` having a faster path in some special cases, but they see that as an unimportant feature, that's way lower on the list of priorities, and they aren't convinced it's even worth the added complexity it would bring to the language implementation. Effectively, where some languages say, this abstraction is so cool, because you can swap out the collection for a different one and get a free speed boost, Clojure says: this abstraction is so cool, because there is no collection you can switch too that would make the performance degrade. So when it comes to performance trade offs, Clojure focuses on making the default and most straightforward way to implement something "fast enough" and scalable to larger inputs. You can think of this as for most use cases, the time it takes for a O(1) will be sufficient for the user, and your program won't choke if your input size grows larger. And in the more exceptional cases where the O(1) isn't fast enough, or you have ridiculously large inputs beyond what even the common "at scale" use cases are. Well for those, Clojure wants to quickly make you realize you should not try to use the default and most straightforward way to implement this, but instead you need to immediately design for that performance. And this isn't black or white either, there are cases where something was deemed worth having a faster internal implementation or special case, because it would have a substantial overall impact, for example with chunked sequence and transducers, or with how small maps are made into an array map, or with transients, etc.