Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Drop millions of allocations by using a linked list

github.com

Post reply on HN
Print view View original

71–80 of 158 posts

Re: Drop millions of allocations by using a linked list

#71

Post by Ao7bei3s »

DiabloD3 wrote: post #62
steipete wrote: post #3

Ruby people discovering algorithms ducks

Not sure why parent is getting downvoted, there is a serious problem in the Ruby community that very few of them have read GoF, TAoCP, and/or K&R.

Stop jumping to conclusions, and stop throwing around buzzwords.

GoF is a (somewhat C++-centric) book about design patterns that's completely unrelated to the discussion at hand, may not be the best resource to learn about design patterns and has nothing to do with CS.

TAoCP is more like an encyclopedia; actually reading through even one chapter takes a significant amount of effort (if you want to get anything out of it). Try it. (Yes, I've worked with it.)

K&R is a 27 years old, thoroughly outdated book about C. There are better options[1].

[1] Try the 16 years old book "Expert C Programming" by Peter van Linden, which is excellent, even though outdated too.

Re: Drop millions of allocations by using a linked list

#72

Post by bglusman »

mkopinsky wrote: post #70
ryanjshaw wrote: post #61

Earlier quoted context omitted.

Is this even a bug or just a case of "in version 0.1 we'll do this quick & dirty", i.e. unaddressed technical debt? I make a point to keep track of all technical debt in my projects so that I have an easy way to quickly identify opportunities for improvements when there is spare capacity, and also so that technical debt isn't left unaddressed.

How do you keep track of the technical debt? Ticket system?

Shameless plug: https://github.com/bglusman/debt_ceiling

Re: Drop millions of allocations by using a linked list

#73

Post by kybernetyk »

mkopinsky wrote: post #70
ryanjshaw wrote: post #61

Earlier quoted context omitted.

Is this even a bug or just a case of "in version 0.1 we'll do this quick & dirty", i.e. unaddressed technical debt? I make a point to keep track of all technical debt in my projects so that I have an easy way to quickly identify opportunities for improvements when there is spare capacity, and also so that technical debt isn't left unaddressed.

How do you keep track of the technical debt? Ticket system?

    //TODO:

    //FIXME:
;)

Re: Drop millions of allocations by using a linked list

#74

Post by picks_at_nits »

WickyNilliams wrote: post #63
steipete wrote: post #3

Ruby people discovering algorithms ducks

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 manner, and the reverse: To understand algorithms that bisect lists in this manner, you have to be familiar with a linked list.

So... Yes it’s a data structure, but it’s joined at the hip to the algorithms that operate best on it.

Re: Drop millions of allocations by using a linked list

#75

Post by Dewie »

robmccoll wrote: post #35
Swizec wrote: post #19

Earlier quoted context omitted.

I keep repeating myself on Hacker News, but once more, we've found the difference between Software Engineer and Computer Scientist. One makes things work, the other is a mathematician. Why do we keep conflating the two?

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 "engineer" is a protected title wherever that person lives.

[1] Note that I said "most programming".

Re: Drop millions of allocations by using a linked list

#76

Post by jokoon »

I still can't see the real usefulness of linked lists, the idea of having a data container that doesn't have a transparent indexing algorithm sounds ill-advised.

Linked lists should be named "linked graphs" instead.

There is so much relevant science to learn about CPU caches, than there is about using a container which is based on nested pointer indirections.

Re: Drop millions of allocations by using a linked list

#77

Post by agentultra »

jokoon wrote: post #76

I still can't see the real usefulness of linked lists, the idea of having a data container that doesn't have a transparent indexing algorithm sounds ill-advised. Linked lists should be named "linked graphs" instead. There is so much relevant science to learn about CPU caches, than there is about using a container which is based on nested pointer indirections.

The only thing I can think of is when your algorithm is building the sequence of items whose length cannot be precalculated. For lists of a certain size you might be able to save over the amortized cost of calling realloc on an array.

Just have to follow the data and watch how its used and build your program to provide the simplest flow.

Re: Drop millions of allocations by using a linked list

#78

Post by varjag »

mkopinsky wrote: post #70
ryanjshaw wrote: post #61

Earlier quoted context omitted.

Is this even a bug or just a case of "in version 0.1 we'll do this quick & dirty", i.e. unaddressed technical debt? I make a point to keep track of all technical debt in my projects so that I have an easy way to quickly identify opportunities for improvements when there is spare capacity, and also so that technical debt isn't left unaddressed.

How do you keep track of the technical debt? Ticket system?

No need to track it, just default on the debt when it's too much to bear.

Re: Drop millions of allocations by using a linked list

#79

Post by shawabawa3 »

richthegeek wrote: post #52
mbrock wrote: post #44

Semi-related: does anyone know why installing gems is so ridiculously slow? What is the thing doing? Downloading tarballs, yes, but then? It's a dynamic language; there is no compilation or verification! Why can I install Ruby packages using apt almost immediately, when gem/bundle install takes half a coffee break? I'm growing more impatient with the years. I have measured out my life with slow software. We talk abou…

Not that I install gems very often (Node.JS is my primary platform) but I find that the majority of the time is installing the different docs. Check the difference between "gem install sass" and "gem install sass --no-rdoc --no-ri" and be amazed.

Which as far as I'm concerned is a bug.

I don't even know how to view gem documentation, and I've never wanted or needed to. --no-document should be the default

They could make it download the docs on first view

Re: Drop millions of allocations by using a linked list

#80

Post by skj »

bcg1 wrote: 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…

Clearly that would require becoming adept with Ruby, which would require actually looking at Ruby code. That's a bit of a show-stopper.
Post reply on HN