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

Type-safe generic data structures in C

iafisher.com

Post reply on HN
Print view View original

41–50 of 57 posts

Re: Type-safe generic data structures in C

#41

Post by jcelerier »

rurban wrote: post #39
jcelerier wrote: post #34

Earlier quoted context omitted.

> C++ templates are ugly, and the STL is very buggy and limited. Also no security and no performance. source ? at least for performance, it seems that there's not a lot of difference from your own link: https://raw.githubusercontent.com/rurban/ctl/master/docs/ima... and with the stl you don't have to call vec_int_free(&a); manually so I have a hard time seeing how this solution is more secure

I haven't written the STL critic parts yet. The testsuite contains a lot of hints. Major quirks: no proper allocation/resize upfront, when you know how big the resulting vector will be. Also not much help with bulk inserts. (Like a proper set join). The 3 STL's I tested massively overallocate. Unordered containers allow ranges, iterators from some to some, whilst they are unordered by default. This begs for bugs. Ran…

the gigabytes of STL-using C++ code that works just fine shows that most of them aren't serious issues. In ~15 years of C++ I have never had any issues with ranges being pairs, strings (though in my opinion string handling shouldn't be part of programming languages at all - they should just be treated as opaque binary blobs like you would pass to eg zlib or libpng), forward_list...

Also, all the interfaces of the STL being quite precise mean that

> Set and hashmaps have to use the slowest datastructures, because they considered better ones as too experimental. Hence no open hashmaps, just chained and rb trees. Their arguments of pointer and iterator stability is just an excuse after this decision. Everybody can work around that, and use open hashmaps and btree's just fine. > No sorted vectors, no small (stack) vectors.

are non-issues: in my own software I can swap std::unordered_map, std::vector, etc... trivially for other containers only by changing their type and adding an include. e.g. in my codebase I have some boost::small_vector, boost::static_vector, pod_vector, flat_set, flat_map, and 4/5 different hash maps which are all chosen specifically for their performance characteristics on various use cases.

In particular if it was C instead, I would have had to change every single call to add, remove, iterate, etc. every time.

Re: Type-safe generic data structures in C

#42

Post by mhh__ »

ginko wrote: post #35

>The rise of a new generation of low-level programming languages like Rust, Go and Zig has caused C and its primitive type system to fall into some disrepute. One of these things is not like the others. I never understood why Go, being a garbage collected language, is grouped with systems programming languages like C or Rust. If anything its direct competitors performance/productivity-wise are probably C# or Java.

The vast majority of programs written in those languages are still relatively simple A->B things like grep or ls was when C was new. Go is a much simpler language than C# and Java - the GC isn't really the point.

Everyone likes to think, I can't use a GC for my work - I don't like garbage collection much either, but this is basically religion: it's just a tool, and it's a tool that makes programming easy.

Re: Type-safe generic data structures in C

#43

Post by mhh__ »

bitwize wrote: post #28
macintux wrote: post #8

Earlier quoted context omitted.

C is still, I have to imagine, the closest thing we have to a language available for all platforms that exist today, while C++ is heavily burdened with featuritis and Rust is limited in platform support.

> Rust is limited in platform support. Rust supports everything you are likely to see in the wild outside of highly, highly specialized applications (e.g. ancient mainframes, satellites from the 80s or 90s, etc.). For God's sake, it's becoming increasingly difficult to justify writing code that takes into account CPU endianness, because all CPUs that are likely to run your code are little endian!

Rust can generate code for many targets yes but there might not be a runtime or peripheral support.

D benefits immensely from a GNU backend - GCC is still top dog for wacky platforms I find

Re: Type-safe generic data structures in C

#44

Post by tom_mellior »

Aanok wrote: post #32
lasagnaphil wrote: post #2

A much more simple alternative way of doing this is to use stretchy buffers. Here's an example of a dynamic array in C in about 20 lines: http://nothings.org/stb/stretchy_buffer.txt And here's a friendly explanation of how this technique works: https://ourmachinery.com/post/minimalist-container-library-i...

> assert(p); > if (p) { Do you want me to have an embolism?

Haha. I was amused/bewildered by:

    void *p = realloc(...)
    // ... cast every other occurrence of p to (int *) ...
The concept may be interesting, but this particular implementation is needlessly horrible.

Re: Type-safe generic data structures in C

#45

Post by tom_mellior »

addaon wrote: post #4
lasagnaphil wrote: post #2

A much more simple alternative way of doing this is to use stretchy buffers. Here's an example of a dynamic array in C in about 20 lines: http://nothings.org/stb/stretchy_buffer.txt And here's a friendly explanation of how this technique works: https://ourmachinery.com/post/minimalist-container-library-i...

But this entirely misses the "type safe" part...

My understanding is that if you declare

    some_concrete_type *p;
    some_other_type x;
then, for example,

    sbpush(p, x);
will result in a type error as expected, since its core expands to:

    p[some_index] = x;
So this is kind of type safe. There is an assumption that

    ((int *) ) + 2
will still be correctly aligned for any type. That's a pretty fair assumption on modern hardware, except maybe for SIMD types.

Re: Type-safe generic data structures in C

#46

Post by tom_mellior »

stkdump wrote: post #38
fulafel wrote: post #37

Earlier quoted context omitted.

I guess because it calls itself a systems language and GC works fine for most systems programming.

What is the defining characteristic of a 'systems language', and what is an example for a language that doesn't fulfill it?

> What is the defining characteristic of a 'systems language'

The precise technical definition is "whatever the speaker means by it". In other words, it's not a useful term.

People will come up with definitions like "whatever you can write an OS kernel/a compiler/a database management system in". So languages like Haskell, OCaml, and Java are certainly included. I don't see why Go shouldn't be.

Re: Type-safe generic data structures in C

#47

Post by fulafel »

stkdump wrote: post #38
fulafel wrote: post #37

Earlier quoted context omitted.

I guess because it calls itself a systems language and GC works fine for most systems programming.

What is the defining characteristic of a 'systems language', and what is an example for a language that doesn't fulfill it?

Well, systems programming and apps programming are the domains in question, SP is about implementing the platform and infrastructure. There is no single defining characteristic since languages are used cross purposes, it's a term meant to characterise existing engineering practice. But if you really wanted an example of the least likely SP language, I'd say MATLAB or Prolog could be nominated.

Lisp and Java have been used in SP roles even though people often think of them as apps languages.

Probably most useful is to observe what usage languages see. Eg Go is used for many databases, K8s, gVisor, Docker etc.

Re: Type-safe generic data structures in C

#48

Post by jcelerier »

lionkor wrote: post #40
bitwize wrote: post #28

Earlier quoted context omitted.

> Rust is limited in platform support. Rust supports everything you are likely to see in the wild outside of highly, highly specialized applications (e.g. ancient mainframes, satellites from the 80s or 90s, etc.). For God's sake, it's becoming increasingly difficult to justify writing code that takes into account CPU endianness, because all CPUs that are likely to run your code are little endian!

> all CPUs that are likely to run your code are little endian Alright, I'll bite. How is ARM (commonly Bi-Endian) considered a (1) "highly specialized" or (2) little-endian architecture?

99% of ARM usage is done in little endian. all android & ios phones, all embedded boards that ship with linux, etc. are always configured in little endian.

Re: Type-safe generic data structures in C

#49

Post by lionkor »

jcelerier wrote: post #48
lionkor wrote: post #40

Earlier quoted context omitted.

> all CPUs that are likely to run your code are little endian Alright, I'll bite. How is ARM (commonly Bi-Endian) considered a (1) "highly specialized" or (2) little-endian architecture?

99% of ARM usage is done in little endian. all android & ios phones, all embedded boards that ship with linux, etc. are always configured in little endian.

Okay, assuming you're right, how much overhead is it to consider endianness? I've never had issues with it, unless I'm implementing something fully from scratch, and that's rare in a production environment.

Re: Type-safe generic data structures in C

#50

Post by ganafagol »

iafisher wrote: post #9

Author here. I wish I had made it clearer that the intent of the post was "this is an interesting and surprising thing you can achieve in C" and not "this is a good idea for a real software project" or "this is a reason to use C instead of C++/Rust/Go".

By the way, the "safe" alternative in your post roughly describes how C++ started its life.
Post reply on HN