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

I write type-safe generic data structures in C

danielchasehooper.com

Post reply on HN
Print view View original

191–196 of 196 posts

Re: I write type-safe generic data structures in C

#191

Post by gpderetta »

monkeyelite wrote: post #190
gpderetta wrote: post #143

Earlier quoted context omitted.

The irony is that arrays in C are in fact generic. As that is the simplest generic solution that doesn't require boiling the ocean first, that's what many programmers reach for.

How do I write a C function which operates on array of type T? Which generic operations does the language provide?

Arrays are generic, but of course C doen't provide generic functions.

You can generically copy arrays [1], index them, iterate them, compute their size. But that's not the point, the point is that you can instantiate them for any (complete) T.

[1] well, C is weird, so you first need to wrap them in a struct.

Re: I write type-safe generic data structures in C

#192

Post by cb321 »

monkeyelite wrote: post #188
dwattttt wrote: post #184

Earlier quoted context omitted.

Resizing has to happen regardless of the ability to delete a key, unless you know upfront how many entries you're going to add; I'd be much more worried about a home grown hash table's tuning to rebalance itself at say, 80% buckets full. If you _do_ know how many entries you're going to be adding upfront, you probably don't even want a hash table, you're probably better off with an array!

You didn’t answer my question. > I'd be much more worried about a home grown This is rhetorical framing. As a knuth reader you should know then when you look inside the box you find some other idiot’s home grown thing who never read the research.

> look at the major standard libraries for hash tables

I don't know what would count as "major", but at least to me "major" does not imply "good". As I mentioned, this idea is ancient (the point of citing Knuth from over half a century ago - that was me, not @dwattttt) but also weakly disseminated. In said weakness, it may well be uncommon in "major" impls, but that merely recapitulates my point. Honestly, that and the resizing thing was such weird argumentation that I didn't take the time to reply.

One does usually resize on insert to keep things sparse as @dwattttt mentioned. With deletions, might want to resize after delete to keep things dense which could help if you iterate over the table much after deleting a lot of it. That is not a cost you would ever pay if you don't delete. So, ability to delete is still something insert-only workloads don't pay anything for.

Moving past the off-point qualification of "major"-ness & weird resize points, if you are actually curious about more details how this can work and want a concrete example, you could look at the Nim stdlib Table implementation: https://github.com/nim-lang/Nim/blob/fbdc9a4c19aafc25937aaa5... or you could read the Knuth subsection that I referenced, but Knuth uses a rather archaic linear probing to smaller indices which probably seems unnatural to modern readers. There is nothing special added to the insert-only data/pathways to support deletes either in that Nim code or the Knuth.

Deletes done this way can benefit from saving integer hash codes (and that happens to be done in the Nim example), but so do all finds via prefix compare & resizes by avoiding hash(). So, in the space-time trade-off analysis of "is saving hash codes worth it?", delete finds & backshifts are just one more part of some workload. This is "deletes in a workload impact space-time trade-offs", though, not "ability to delete costs insert-only workloads" which seems to be the contentious point.

Re: I write type-safe generic data structures in C

#193

Post by el_pollo_diablo »

monkeyelite wrote: post #187
el_pollo_diablo wrote: post #186

Earlier quoted context omitted.

You mean the downside that we also already know, i.e. that there are some situations where a custom data structure would be superior for various reasons (e.g. smaller footprint)? Experienced programmers know when to reuse a generic library and when to roll out their own. We all know that. Yet you dismiss generic red black trees because there is no realistic single program that uses 10 key/value combinations. Not only…

> Yet you dismiss generic red black trees I use generic data structures all the time. That’s the default in programming. We know their advantages. I am trying to say there is a world out there that doesn’t look like ours and it works just fine and has other advantages. Are you saying the only real way to program is with generic data structures? I’m saying no because nobody did prior to the late 80s. > I am definitely…

> Are you saying the only real way to program is with generic data structures?

Certainly not. As I said, the experienced programmer knows when (not) to use them. Some programs are better off without them, such as... most of the low-level software I write (security-critical operating systems).

> Data tends to follow a particular path and there is probably 1 red black tree and it’s a core feature of the application. If that’s true then it’s not a big deal to write that core feature of your application.

"It's not a big deal" are famous last words. Maybe it is not a big deal, but unless you have hard constraints or measurements that confirm that you would not be served well enough by an existing solution, it may very well be the reason why your competitors make progress while you are busy reinventing, debugging, maintaining, and obtaining certification for a wheel whose impact you overestimated.

> It avoids premature optimization and code bloat because you tend to use complex data structures when they have a need.

Avoiding code bloat? Agreed, a custom solution cannot be worse than a generic one. Avoiding premature optimization? Quite the contrary: going straight for the custom solution without first confirming, with actual measurements, that the generic solution is the unacceptable bottleneck, is textbook premature optimization.

I am sorry but I do not understand what you are getting at.

Re: I write type-safe generic data structures in C

#194

Post by el_pollo_diablo »

antonvs wrote: post #155
el_pollo_diablo wrote: post #125

Earlier quoted context omitted.

Not to mention that they insist on calling every entry of the list a "list head", which makes no sense (hysterical raisins, maybe?). The structure is made of a uniform loop of entries, one of which is used as the actual head & tail, or entry point into the structure.

In general, there is no “actual” head and tail - you could have multiple references to different parts of the list, and each of them would have a different head. If you’re recursing through a list, at some point every node will be used as the head. This is a common pattern in recursive data structures, particularly in functional languages. Disclaimer: I haven’t looked at this author’s code, just pointing out that lis…

Head and tail make sense for persistent lists in functional languages with value semantics, yes.

The intrusive, mutable, doubly-linked loops with reference semantics under discussion are quite different. Although all entries behave identically in the structure itself, one of them is _used_ differently, as a standalone anchor point, while the others are embedded in the list's "elements".

Re: I write type-safe generic data structures in C

#195

Post by wahern »

teo_zero wrote: post #154
wahern wrote: post #147

Earlier quoted context omitted.

By tagged they mean have an identifier. Compare > struct { ... } foo; and > struct bar { ... } foo; The latter has an identifier, bar; the former doesn't. The standard uses tag to refer to the identifier name, if any, in an enum, struct, or union declaration.

Exactly, thank you. I've always called "tag" the id that optionally follows struct/union/enum. Is it the wrong word? Some specs call it "name", but "unnamed union" sounds dangerously similar to "anonymous union", which is a different concept, namely (no pun!) an unnamed member of an outer struct or union whose submembers can be accessed as if they belong in the outer one. E.g. struct { struct { int m; }; // no name:…

Yep, tag is the correct terminology. See, e.g., section 6.7.3.4 Tags in N3220 (https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3220.pdf)

Re: I write type-safe generic data structures in C

#196

Post by rucikir »

dhooper wrote: post #55
wahern wrote: post #51

Earlier quoted context omitted.

FWIW, as far back as 2015 my feature check library documents Visual Studio as supporting "__typeof".[1] Note the leading but not trailing underscores. Perhaps I was mistaken, but I usually tested that sort of thing. It's also possible __typeof had slightly different semantics. [1] See https://github.com/wahern/autoguess/blob/b44556e4/config.h.g... (that's the 2015 revision, but HEAD has the same code).

msvc 19.39 is the first to support it, which I mention in the article. You can confirm it didn't work up through 19.38 in godbolt [1]. I don't use Visual Studio, so I don't know what version of that first started using msvc 19.39 [1] https://godbolt.org/z/M7zPYdssP

Playing with MSVC's typeof, I've just discovered that its docs [1] have an example that has never worked with any released version of MSVC... MSVC doesn't support `typeof` applied on function types and function pointers! (bug report [2] [3]). Is there anyone from the compiler team around here? :)

[1]: https://learn.microsoft.com/en-us/cpp/c-language/typeof-c?vi... [2]: https://developercommunity.visualstudio.com/t/Support-for-ty... [3]: https://gcc.godbolt.org/z/Kn51qrj99

Post reply on HN