Live data from Hacker News

Drop millions of allocations by using a linked list

github.com

81–90 of 158 posts

Re: Drop millions of allocations by using a linked list

#81
post #75

Earlier quoted context omitted.

You should be careful with the term engineer. By definition, engineering is the application of scientific and mathematical knowledge to solving practical problems. Without knowing and understanding the science and math behind computing and software, one can hardly claim to be a software engineer.

So many programmers have this weird inferiority complex when it comes to the term "engineer". Not you, but those who think that most programming can never be called "engineering" because people don't die if you introduce a software bug[1] (as if the only kinds of modern "engineers" have to do with immediately safety-critical things). I prefer the plain "programmer" myself, but I don't see the big deal unless "enginee…

I'm a little sheepish about using it around the engineers in my life because I know I'm not legally liable and held accountable to the same standards they are when I make a mistake in the software I ship.

I like to think I take a certain amount of rigor in the choices of tools and processes and design philosophy that reduces the amount and impact of bugs... but if we get a customer complaint about our product we don't generally issue a recall and lose millions of dollars.

It's not that I spend any less time learning theory and application and it's certainly no less challenging in some cases than even mechanical engineering but... it's a liability thing.

Also, I don't write software for aerospace control systems.

I've seen companies advertise "software engineer," positions whose primary responsibilities included running a fleet of Wordpress blogs.

Just a matter of perspective I guess.

Re: Drop millions of allocations by using a linked list

#82
post #26
post #3

Ruby people discovering algorithms ducks

Java had the same kind of issue for years. In Java and Ruby, the standard library uses an object `+` operator to mean concatenation (not numeric addition), and the implementation did immediate data copies, rather than doing reference linking and copy-on-write (or immutability).

But in Java this happens only with strings doesn't it?

Re: Drop millions of allocations by using a linked list

#83
post #6
post #3

Ruby people discovering algorithms ducks

Really. Every time I whine publicly how web programming people aren't familiar with even basic CS, I get a slap. But really, I should move to web programming. I'll be an expert computer scientist there, probably.

You probably wouldn't do that well in web development, because it's too different from embedded or systems programming.

You probably have the luxury of specializing in one particular language, and maybe a handful of processor architectures. You probably rely on one or a few libraries, and know them backwards and forwards. You probably have your own personal repository of code and tactics that you go back to often. In other words, your knowledge of programming is probably narrow and deep.

Web developers usually don't get that luxury. Top web developers today have to be fluent in a minimum of two programming languages (javascript and a backend language like Python, Ruby, PHP...), use several different fast prototyping approaches (css compilers and wacky templating systems), have a good working general knowledge of everything from the web browser to the web server, and cope with an environment in which at least one of those parts is changing on almost a daily basis. Web development is shallow and very, very broad.

I prefer systems programming but I've worked as a web developer off and on for several years now. I have a lot of respect for any web developer that's really good at it. They aren't lesser programmers at all, and I suspect a lot of them, if they decided to do it, could kick the pants off of most systems programmers.

Re: Drop millions of allocations by using a linked list

#84
post #51

I'm really surprised by the amount of smugness in the comments here. A bit of good-natured teasing, followed by a wheelbarrow full of "ruby-devs" this and "web-devs" that. Take off your Hats of Superior Coding. Any one of us, regardless of honorific titles, could have made this mistake, and you know it. Being steeped in CS Fundamentals does not immunize you against bugs. Congratulations to tenderlove for finding the…

Is this legitimately a bug, though? It could be tagged as a performance defect, but there is code like this through projects across the land.

I think the reason this rubs some people the wrong way is that implementations like this can be the result of the "no premature optimizations!" philosophy and its advocacy. I've encountered this firsthand at a number of organizations, and it apparently was somewhat endemic in the Ruby space.

Make something that works, and benchmark later to find that one magical hog that you can quickly change and then everything is optimal. Only it almost always ends up being a performance death by a thousand (million) cuts, performance and resource malaise so endemic that fixing it almost seems impossible.

Re: Drop millions of allocations by using a linked list

#85
post #51

I'm really surprised by the amount of smugness in the comments here. A bit of good-natured teasing, followed by a wheelbarrow full of "ruby-devs" this and "web-devs" that. Take off your Hats of Superior Coding. Any one of us, regardless of honorific titles, could have made this mistake, and you know it. Being steeped in CS Fundamentals does not immunize you against bugs. Congratulations to tenderlove for finding the…

Thanks, I really appreciate the kind words! <3<3<3<3

Re: Drop millions of allocations by using a linked list

#86
post #39
post #34

Earlier quoted context omitted.

AFAICT, this performance bug is not at all related to the linked-list vs. vector issue.

Yes it does: vectors are good for random access, linked-lists are good for doing stuff in the front/back of the list. The performance bug we have here is solved by finding a way to insert stuff at the front/back (and also going through each item in the list); there is no need for random access.

Vectors are good at inserting in the back and deques are good in inserting both in the front and in the back (or course if capacity grows exponentially, but that's how they should be implemented). Linked lists are almost always wrong choice because they don't play well with memory caches. They might be better with inserting in the middle and that might matter only with really huge lists (millions of items). At least that's how it works with languages close enough to the hardware.

Re: Drop millions of allocations by using a linked list

#87

Earlier quoted context omitted.

In a certain, quite limited model of economics that could actually be named as "wise". Once a more holistic view is taken, wide spread total costs and benefits are taken into consideration, once costs are not only defined as money flowing out of my own pocket, once not only "Gesinnungsethik" but also and more importantly "Verantwortungsethik" gets applied, well, in such a world we would probably wish, that Amazon wou…

What social changes would you expect from the pricing policy changes of marginal EC2 instances?

"social changes from the pricing policy changes of marginal EC2 instances" sounds ridiculous when given this context, right?

It changes when the context are not "marginal EC2 instances" but instead energy and resources burning machines, used (often) by ignorant software developers and their organizations allowed and actually encouraged, partly even actively driven into such purely self beneficial behavior models.

For a definition of social: http://en.wikipedia.org/wiki/Social ... obviously driving software development into a scarcity of computing power would haven "social" consequences: in the development teams f.e. interactions and priorities would need to change dramatically.

But maybe software development turned almost into a "commodity" because of the commoditization of computing power available to even the most ineffective mental artifact aka program.

And that in turn was possible in large extent by off-loading the true costs of assembly / dis-assembly / disposal and the resources needed to build those machines onto people in underdeveloped regions of the world...

Now what could the social change be, the more expensive computing devices could allow for in those regions?

If people cared about "effectivity" not only via a detour to "uh, i need to recharge my phone, again?!" f.e. but essentially because because they would have to pay the true cost for their ineffective setup of hardware and software?

What could the social change be... ;)

Re: Drop millions of allocations by using a linked list

#88
post #59

I'm not a ruby dev, so I guess maybe my perspective is not that great on this particular issue... but hats off to the dev with the fix, indeed this is how free software collaboration is supposed to work in my opinion. Even the dev with the fix wasn't rude about the original problem, he seemed pretty humble about it actually. If you think the Ruby guys are such shitty programmers you should be able to dive into their…

> Even the dev with the fix wasn't rude about the original problem, he seemed pretty humble about it actually.

The Ruby community is very good interpersonally from my experience. It's a culture that I think comes from this:

http://en.wikipedia.org/wiki/MINASWAN

Re: Drop millions of allocations by using a linked list

#89
post #51

I'm really surprised by the amount of smugness in the comments here. A bit of good-natured teasing, followed by a wheelbarrow full of "ruby-devs" this and "web-devs" that. Take off your Hats of Superior Coding. Any one of us, regardless of honorific titles, could have made this mistake, and you know it. Being steeped in CS Fundamentals does not immunize you against bugs. Congratulations to tenderlove for finding the…

Smugness: the dark-side of hubris. Hubris being one of the three virtues [0].

I like to remember the past of computer programming as though it was once friendly and receptive to people of all skill levels. I owe quite a lot to the geeks who came before me and answered my stupid questions, gave me powerful tools to learn with, and accepted my contributions; flawed as they were. Without making a few mistakes along the way I wouldn't be where I am today.

I don't know whether I would have given up if the people I met were more smug and mean-spirited but my progress might have been slowed by it. Life is too short to waste bothering with people who are miserly with their good fortunes. It doesn't cost you anything to be nice and share your knowledge and wisdom. It may pay off when the person you're sharing with rises to stand upon your shoulders one day and pay homage to you.

[0] http://threevirtues.com/

Re: Drop millions of allocations by using a linked list

#90

Earlier quoted context omitted.

Um... isn't this a data structure not an algorithm?

Programs = Data Structures + Algorithms, and it is often the case that there are deep relationships between the data structures and the algorithms. For example, any linear recursive algorithm that deals with the head of a list and the tail/rest/butHead of a list is optimized for a linked list implementation. So... to understand a linked list, you really need to be familiar with algorithms that bisect list sin this ma…

I know, I was intentionally curt in my reply because snark is best solved with more snark
Post reply on HN