>but hardly means that we should be against writing fast software.
On the contrary.
Lisp is slow. Python is slow. Ruby is slow. Smalltalk is slow. What do these languages have in common? Dynamism. They trade speed for other that were, in the language designer's opinion, equally or more important than being fast.
The point is, that when you make a decision about performance, the decision has consequences in either direction. LLs are slow, but they have a lot of advantages. With skip lists you can get decent access tumes on ordered LLs, and in some contexts even O(n) is acceptable. But what LLs do better than other list structures like arrays is insertion. With an array, you get best-case O(1) appends, but all other types of insertion are O(n), and even appends can be O(n) if you run out of space and have to reallocate.
By contrast, provided you have a pointer to the location in the LL that you want to insert at (which is why most LL uses in applications like to insert at the head of the list), LL insertion is guaranteed O(1). That's sometimes useful.
Most of the time you should, I'd say. Regardless, the decision should be very natural/ trivial for any developer - understanding the performance attributes of the most common data structures is not asking too much of developers.
> They trade speed for other that were, in the language designer's opinion, equally or more important than being fast.
Yes, of course. I am not advocating for highly tuned software - I've stated as much in the last post. There are often tradeoffs.
No one is arguing that a linked list is not more algorithmically efficient at certain things. What I will say is that Vectors still end up faster for most operations, and it shouldn't be hard for a developer to determine when those situations arise.
I am not arguing against LL. I am just saying that it isn't 'lunacy' to understand basic performance characteristics of your software. Your post essentially came off, at least to me, as "people are crazy for wanting ot use a more efficient data structure".
It's not: it's very important.
>Your post essentially came off, at least to me, as "people are crazy for wanting ot use a more efficient data structure".
My point was more that people aren't necessarily crazy for using an LL. I don't, however, think that anybody is crazy for choosing not to use one for perf reasons.
I guess what I'm saying is that AFAICT, we're entirely in agreement, and I have no idea why we thought we weren't.
I find that taking these lessons to database access patterns helps a lot. Know your data access, and the data structure design has meaningful discourse. Don't know your access patterns? You are unable to pick the best one. Period.
Pretty much: if you don't know the access patterns, draw up a naive implementation so you can figure them out.
This is actually connected to one of the disadvantages of Lisp: because Lisp makes it so easy to draw up a naive datastructure based on LLs, it can take some effort to rip all that out and make something actually fast in its place.
>I wouldn't say it is the dynamism as much as the lack of control.
Don't undereatimate the cost of runtime dynamism. Lisp compilers have gotten pretty good at avoiding implementing it when possible, but there are pretty tight limits on how far you can go with that sort of optimization.
Essentially, every time you call a CLOS method, or you use eval, or you in any way introspect on your runtime state, or create the possibility for your code to do so at runtime, the code you are writing becomes more costly to run.
I view it as reducing the coefficient of writing a program. This means more will be made. So more slower ones will get made.
However, nothing prevents you from writing a fast program in that language. Other than the slower successes.
Suppose you're required to solve a problem with very high performance, and it has to be expressed in some high level language. No high level language achieves it using any straightforward code without dropping to assembly language. Not C, nothing.
In that situation, I'd arm myself with Lisp, because the problem basically requires inventing some specialized fast language and mapping it to the machine at hand.
I would also challenge that 99% of all applications are disk bound but I think it's really besides the point. Really, the argument is that performance doesn't matter in all situations, which is true, but hardly means that we should be against writing fast software.