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

Fast linked lists

dygalo.dev

Post reply on HN
Print view View original

121–130 of 131 posts

Re: Fast linked lists

#121

Post by sumtechguy »

josephg wrote: post #98
sumtechguy wrote: post #96

Earlier quoted context omitted.

I used to use them all the time. However, now? I would be hard pressed to not use one of the many built in vector/list/dict/hash items in many languages now. I would have to be truly doing something very low level or for speed to use one.

As a counterpoint, I’ve been working on collaborative text editing. I ended up implementing a custom b-tree because we needed a few features that I couldn’t find in any off the shelf library: - My values represent runs of characters in the document. - Inserts in the tree may split a run. - Runs have a size - 0 if the run is marked as deleted or the number of characters otherwise. The size changes as we process edits…

> I love this stuff. I think it’s pretty rare to find a reason to code your own collection types these days, but it certainly comes up from time to time!

Absolutely! That is one of the places you want to use that style of programming. As the base classes and built in structs do not really cover it yet.

Also as a counterpoint sometimes the built in ones have some very interesting degenerate cases. I had one in an old library that basically doubled its memory footprint every time you exceeded its buffer. That was a point to change it to be a fixed allocation or something else. If i had no idea of the fundamentals I would have been totally in the weeds and no idea why it was doing it.

Re: Fast linked lists

#122

Post by 9659 »

coldtea wrote: post #59
9659 wrote: post #49

Earlier quoted context omitted.

1%

More like 0.01% -- if we consider enterprise programmers, web programmers, and application/game programmers which I'd expect to be the largest groups...

if the value really is 0.01%, then the education pipeline needs to be revised. 'blue collar' programmer positions should be the majority.

Re: Fast linked lists

#123

Post by cyberax »

dist1ll wrote: post #102
cyberax wrote: post #71

Earlier quoted context omitted.

In kernels, it's usually hard to get general-purpose allocation working reliably in all contexts. And you need that for resizable vectors. With lists, you just need to be able to grab an element-sized block. Quite often, it's even done with the memory page granularity. In addition, a lot of data structures might be shared across multiple cores. Linked lists can be traversed and mutated concurrently (although with a b…

I wonder how much of that is due to the kernel history, and the influence of C idioms, and not because of some inherent design superiority. I'd be convinced once I see pure Rust kernels geared towards modern machines suddenly using linked lists everywhere. Otherwise I'm leaning towards it being a side-effect of the language choice and culture. Also because I've seen the same kind of reasoning applied to compilers (e.…

Getting a general memory allocator working in kernel contexts is a hard task. You need to make sure it can't block and is re-enterable, that it doesn't result in fragmentation, and that it can be used from multiple threads.

It can be solved (or worked around), but it's understandable that people don't _want_ to do that.

Re: Fast linked lists

#124

Post by samatman »

kazinator wrote: post #115
samatman wrote: post #107

Earlier quoted context omitted.

You need a linked list to write hello world in any Lisp, though. Seems like the glaring exception to the rule!

No, you don't need to use linked lists to send a string to the standard output port in most Lisps. You just call a function.

(write-string "hello world") has linked list semantics, the fact that compilers can be smart enough to ignore this is not the point I'm making.

(write-string (cdr '(write-string "hello-world"))) also has to work, so it's pretty easy to materialize that semantics at any point.

Re: Fast linked lists

#125

Post by kazinator »

samatman wrote: post #124
kazinator wrote: post #115

Earlier quoted context omitted.

No, you don't need to use linked lists to send a string to the standard output port in most Lisps. You just call a function.

(write-string "hello world") has linked list semantics, the fact that compilers can be smart enough to ignore this is not the point I'm making. (write-string (cdr '(write-string "hello-world"))) also has to work, so it's pretty easy to materialize that semantics at any point.

> has linked list semantics

Nope; it has linked list syntax (that certainly isn't ignored even by very good compilers). Syntax isn't semantics.

The semantics is that a function write-string is called, with a string as its argument.

The second expression has linked list processing in its semantics because you stuck in a cdr, as well as a quote which makes a piece of the program available as run-time list datum. (This is semantics that could be easily optimized away in the executable form, but I would say that it has linked list processing in its abstract semantics.)

Re: Fast linked lists

#127

Post by aldanor »

ComputerGuru wrote: post #42
duped wrote: post #14

It strikes me the bottleneck for this problem isn't Vec or List, it's the serde_json Value type that needs to be used. This is useful for serializing/deserializing values into Rust types but if you're trying to validate JSON against a schema you don't actually need the JSON value data, just the types of the nodes (or more specifically, you only need some of the value data, and probably not much of it, so don't pay fo…

> All that said, serde_json is incredibly convenient and giving up to write your own parser is a big hammer for a problem that probably doesn't need it. I had a thought in my reply [0] on this that actually might let him eat his cake and have it too in this regard. I think you can heavily abuse serde::de::Visitor to schema validate without actually parsing (or with less parsing, at any rate). I went into more detail…

Or, use sonic_rs::Value which uses simd and arena allocation for keys and in my case for big payloads was 8x faster than serds_json.

Or, use sonic_rs::LazyValue if you want to parse json on demand as you traverse it.

Re: Fast linked lists

#128

Post by coldtea »

9659 wrote: post #122
coldtea wrote: post #59

Earlier quoted context omitted.

More like 0.01% -- if we consider enterprise programmers, web programmers, and application/game programmers which I'd expect to be the largest groups...

if the value really is 0.01%, then the education pipeline needs to be revised. 'blue collar' programmer positions should be the majority.

This not about blue collar vs white colar. After all corporate programmers and web programmers can both be blue colar, and systems programmers can be white colar (if we're using "blue colar" to mean smaller salaries and fewer percs - otherwise programming is a white colar job anyway).

This is about how many work in kernels/embedded systems/etc vs more common programming gigs. And that's less about how many are trained to do so, but rather how many are needed.

Re: Fast linked lists

#129

Post by ComputerGuru »

aldanor wrote: post #127
ComputerGuru wrote: post #42

Earlier quoted context omitted.

> All that said, serde_json is incredibly convenient and giving up to write your own parser is a big hammer for a problem that probably doesn't need it. I had a thought in my reply [0] on this that actually might let him eat his cake and have it too in this regard. I think you can heavily abuse serde::de::Visitor to schema validate without actually parsing (or with less parsing, at any rate). I went into more detail…

Or, use sonic_rs::Value which uses simd and arena allocation for keys and in my case for big payloads was 8x faster than serds_json. Or, use sonic_rs::LazyValue if you want to parse json on demand as you traverse it.

Hey, that's a nifty looking library. Thanks for pointing it out to me!

Re: Fast linked lists

#130

Post by samatman »

kazinator wrote: post #125
samatman wrote: post #124

Earlier quoted context omitted.

(write-string "hello world") has linked list semantics, the fact that compilers can be smart enough to ignore this is not the point I'm making. (write-string (cdr '(write-string "hello-world"))) also has to work, so it's pretty easy to materialize that semantics at any point.

> has linked list semantics Nope; it has linked list syntax (that certainly isn't ignored even by very good compilers). Syntax isn't semantics. The semantics is that a function write-string is called, with a string as its argument. The second expression has linked list processing in its semantics because you stuck in a cdr , as well as a quote which makes a piece of the program available as run-time list datum. (This…

> Nope; it has linked list syntax (that certainly isn't ignored even by very good compilers)

We're looking at the same string and seeing different things. You're seeing `(write-string "hello world")` as a program, I'm seeing it as an expression.

It has linked list semantics, which you can preserve until runtime like this `'(write-string "hello world")`. Note that I didn't change the string, I changed its context. If the original were living in a string, and you called read on it, it would become a linked list. If you called eval on that list, it would become a function call. This is basic stuff which I'm well aware you know, so I'm not sure what all the quibbling is about.

You literally need a linked list to write a program in a language in which the code becomes linked lists. And you're going to have a bad time writing Lisp if you don't get the hang of cons cells, early and often.

Is "code is data" true, or false? You're trying to have it both ways here.

The "large number of programmers who have learned about linked lists but haven't run into many cases where they needed them in the world world" include approximately zero programmers who have wielded Lisp in anger, is my point. I thought that was pretty clear from context, but I guess not.

Post reply on HN