News for hackers. Stuff that matters.
Re:Computer Science from the Bottom Up (2013) by qwertyuiop924 on Saturday December 24, 2016 @01:31PM (#13251009)
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.
Re:Computer Science from the Bottom Up (2013) by staticassertion on Saturday December 24, 2016 @01:42PM (#13251063)
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.

Re:Computer Science from the Bottom Up (2013) by qwertyuiop924 on Saturday December 24, 2016 @05:16PM (#13251848)
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.

Re:Computer Science from the Bottom Up (2013) by staticassertion on Saturday December 24, 2016 @05:35PM (#13251912)
> 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".

Re:Computer Science from the Bottom Up (2013) by qwertyuiop924 on Saturday December 24, 2016 @07:21PM (#13252228)
>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.

Re:Computer Science from the Bottom Up (2013) by taeric on Saturday December 24, 2016 @07:24PM (#13252243)
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.

Re:Computer Science from the Bottom Up (2013) by qwertyuiop924 on Saturday December 24, 2016 @09:33PM (#13252582)
>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.

Re:Computer Science from the Bottom Up (2013) by taeric on Sunday December 25, 2016 @12:35AM (#13253110)
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.

Re:Computer Science from the Bottom Up (2013) by qwertyuiop924 on Sunday December 25, 2016 @09:37AM (#13254207)
With a compiler smart enough to aggressively cull any uneeded dynamism, it might be possible. But it would still be hard.
Re:Computer Science from the Bottom Up (2013) by kazinator on Sunday December 25, 2016 @11:40AM (#13254607)
A pragmatic view, perhaps, is that as a tool, a given Lisp environment doesn't constraint how fast a solution we can devise to a problem in some manner. That really fast solution might not simply be a Lisp program fed to the Lisp compiler.

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.

Re:Computer Science from the Bottom Up (2013) by qwertyuiop924 on Sunday December 25, 2016 @02:10PM (#13255066)
So a custom Assembler using CL as a macro language? That works.
Re:Computer Science from the Bottom Up (2013) by junke on Sunday December 25, 2016 @03:32PM (#13255321)
Re:Computer Science from the Bottom Up (2013) by kazinator on Sunday December 25, 2016 @03:27PM (#13255297)
If you don't know the access patterns, you can't pick the best representation if the prioritized list of criteria determining "best" begins with access speed. If the list begins with something else, you may still be able to pick the best one.
Re:Computer Science from the Bottom Up (2013) by taeric on Monday December 26, 2016 @12:19AM (#13257074)
Fair. And yes, I was assuming "best" as in the fastest or most predictably bounded.

I did not think I was stating anything profound.