News for hackers. Stuff that matters.
Re:Computer Science from the Bottom Up (2013) by kazinator on Saturday December 24, 2016 @10:45AM (#13250196)
> Increasingly today the underlying architecture, for most intents, is becoming irrelevant

... amidst cries from a handful of lunatics who insist we shouldn't be using linked lists any more because they don't use the L1 cache very well compared to arrays.

Re:Computer Science from the Bottom Up (2013) by gravypod on Saturday December 24, 2016 @11:12AM (#13250288)
In some contexts this optimizations make no sense. In others you'd be laughed out of the office for suggesting that you should use a linked list. You'd be shitcanned before you got back to your office.

In the same sense if you're in a python shop doing web development and you say "EVERYONE we need to STOP using python and write ALL of our HTTP code in C! We'll be able to optimize the hell out of it and probably save 10K of memory per request! That's HUGE!" you would also in tern be shitcanned before you finished the sentence.

If you take that same exact mentality and bring it to a company that builds realtime systems that do DSP and maybe even handle some user interaction in an embeded form facter and you say "EVERYONE! I've found that if we replace our current memory allocator with a circular buffer and pre-allocate everything in an SRAM we can get power-off tolerance AND allow ourselves to make use of all of our memory while not even needing to WASTE the cyles on freeing our memory! We'll save on the oders of 1ms over 50actions! That's a HUGE boon for our batter life!" you'd walk out the head of the office. Saving 500ns, 100 bytes, or even improving something on that scale no matter what it is in contect is huge.

The problem boils down to one thing. For the embeded systems people saving 1MS may be on the oder of 20% of their runtime. For the python shop saving 10K of memory is probably on the oder of sub-00.001% of their memory usage.

It is all about context.

(Disclaimer: I have changed from LL to arrays in some applications because it made a measurable improvement to the speeds of my systems.)

Re:Computer Science from the Bottom Up (2013) by qwertyuiop924 on Saturday December 24, 2016 @01:38PM (#13251043)
Yep. Totally.

Also, if you're working in an HLL, know how LL is implemented in your PL. Because even in Lisp, not all LLs are created equal, and even if you create them the same way, they don't necessarily have the same perf characteristics.

For instance, because Haskell, ML, and the other functional languages don't allow datastructure mutation, they can CDR-code all their lists, something Lisp does as well (which is why list literals created with QUOTE cannot be modified, IIRC). This collpses the linked list structure into something resembling an array, increasing cache response time. Additional conses will be allocated separately, but this will still increase efficiency.

Re:Computer Science from the Bottom Up (2013) by vvanders on Saturday December 24, 2016 @11:15AM (#13250303)
Software is an inverted pyramid, most programmers don't need to know the low-level bits. However if you don't have at least someone to hold up the lower layers of the pyramid then everything falls over.

Performance and memory is one of those weird things where it doesn't matter until it does, and then it really matters. I can't count the number of projects I've been on where there wasn't a way to "scale" out, we had fixed resources and the only path forward was deep low level optimizations.

Re:Computer Science from the Bottom Up (2013) by staticassertion on Saturday December 24, 2016 @11:57AM (#13250511)
Errrr, how is this lunacy? Seems like something everyone should be aware of.
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.