3 ms·

It is, but if you're, say, writing a small-scale webapp or some other app that's disk-bound (99% of all applications), it's probably not something you'll have t

It is, but if you're, say, writing a small-scale webapp or some other app that's disk-bound (99% of all applications), it's probably not something you'll have to worry about.

staticassertion 10y ago
Right but what's the reason not to pick a data structure with better performance? This should be a really trivial choice with virtually 0 impact on code since a list and array will have nearly if not entirely the same interface. 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.
- qwertyuiop924 10y ago
  Of course. But OTOH, we shouldn't immidiately discount LLs when writing code, just because the perf isn't optimal. >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.
  - staticassertion 10y ago
    > Of course. But OTOH, we shouldn't immidiately discount LLs when writing code, just because the perf isn't optimal. 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".
    - qwertyuiop924 10y ago
      >I am not arguing against LL. I am just saying that it isn't 'lunacy' to understand basic performance characteristics of your software. 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.
  - taeric 10y ago
    I wouldn't say it is the dynamism as much as the lack of control. Specifically, if you write your code non idiomatically and control all allocations, the languages probably gain a lot on speed. Unless you need inline assembly. Some lisps allow this. 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.
    - qwertyuiop924 10y ago
      >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.
      - taeric 10y ago
        I am in complete agreement that lisp makes it possible to write slower programs. I just challenge that it is an inherently slower language. 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.
        qwertyuiop924 10y ago
        With a compiler smart enough to aggressively cull any uneeded dynamism, it might be possible. But it would still be hard.

It is, but if you're, say, writing a small-scale webapp or some other app that's disk-bound (99% of all applications), it's probably not something you'll have to worry about.

staticassertion 10y ago

Right but what's the reason not to pick a data structure with better performance? This should be a really trivial choice with virtually 0 impact on code since a list and array will have nearly if not entirely the same interface. 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.

qwertyuiop924 10y ago
Of course. But OTOH, we shouldn't immidiately discount LLs when writing code, just because the perf isn't optimal. >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.
- staticassertion 10y ago
  > Of course. But OTOH, we shouldn't immidiately discount LLs when writing code, just because the perf isn't optimal. 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".
  - qwertyuiop924 10y ago
    >I am not arguing against LL. I am just saying that it isn't 'lunacy' to understand basic performance characteristics of your software. 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.
- taeric 10y ago
  I wouldn't say it is the dynamism as much as the lack of control. Specifically, if you write your code non idiomatically and control all allocations, the languages probably gain a lot on speed. Unless you need inline assembly. Some lisps allow this. 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.
  - qwertyuiop924 10y ago
    >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.
    - taeric 10y ago
      I am in complete agreement that lisp makes it possible to write slower programs. I just challenge that it is an inherently slower language. 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.
      - qwertyuiop924 10y ago
        With a compiler smart enough to aggressively cull any uneeded dynamism, it might be possible. But it would still be hard.