Comment by dbaupp | Hacker News Reader

Comment by dbaupp | Hacker News Reader

Parent Full thread

The lack of generics means your array implementation is either going to either:

- be implemented with macros and token pasting, and result in a ton of mental overhead because you'll have a pile of types like array_foo for an array of `foo`s, and array_bar for an array of `bar`s, along with a pile of corresponding `foo * array_foo_get(array_foo, size_t)` and `bar * array_bar_get(array_bar, size_t)` functions.

- or, have a runtime cost and lose type safety by storing void* and casting when accessing.

The first case is even worse than it sounds: e.g. I don't know how you handle arrays of types with spaces in them (like `unsigned char`, or `struct bar`) with a macro. And, we haven't even thought about const correctness yet, which would probably require having const_array_foo, const_array_bar (etc.) types defined too.

(And, of course, these only solve one facet of the problems with C's pointers: there's no way to defend against use-after-free or dangling pointers.)

C macros-faking-generics really aren't that bad (your "unsigned char" case is really easy to solve - use another macro). It's a bit goofy having different types floating around like "array_of_int", "array_of_float", but you can create them in a single line when needed, and once you create them, they work, and efficiently.

They're not an ideal solution by any stretch, but it's not the nightmare scenario you envision wrt generic data structures in C.

I would be interested in the specifics of the spaces thing (knowing more about ones tools is good) but "10 minutes" to handle all the various issues and bugs that will inevitably pop up from wrangling macros?

Yeah 10 minutes is quite a bit off, at least for me. The various issues and bugs that arose all came about when developing the data structures themselves - they didn't crop up in actual usage. Though my approach was to use a separate header and source file for each new data type I parameterised them by. So I had an "int_array.c" and an "int_array.h". And inside the header would just be function declarations generated by the macro. I basically didn't like the idea of dumping in a whole implementation of a data structure and all its operations with a macro every single time I wanted to use it. YMMV but I found it worked well.

That approach of a single invocation was what I would personally assume would be done (or put it in the header that defines the data type, for a custom one), but I'm not sure how that solves spaces?

No more spaces:

    typedef unsigned char uchar;
    DECLARE_AND_IMPLEMENT_ARRAY_API(uchar)

I actually did this¹⋅² some time ago. Since then I've moved on from a hardcore C developer to C++ and Ada³, but it wasn't necessarily a bad solution. I think given how little C gives you to work with, it's the best solution you can do.

It does make debugging a chore. I ended up with a Makefile rule to run the test suite through the preprocessor (and did some hackery to exclude #include of system headers), format it with clang-format, and build that. Not exactly pretty or easy, but it got the job done.

1. https://github.com/alpha123/yu/blob/master/src/yu_splaytree....

2. https://github.com/alpha123/yu/blob/master/test/test_splaytr...

3. Where this sort of thing is much easier and I am happier and more productive.

Having worked in a code base like this (prior to migration to C++11), I'd agree that they're not necessarily a "nightmare", but they lead to code that's so verbose that it tends to really obscure the actual logic of a piece of code. (Especially anything more complicated than a simple array, e.g. associative maps or multi-dimensional arrays, and iteration constructs can be hellish.)

No, you just allocate enough space to store an extra int at the start for the length, and return a typed pointer to the actual data. Then you need an accessor that checks bounds, if you want safe access. Both of these problems are solved by simple macros.

So you want the array to have type foo * ? Ignoring that this doesn't let the compiler help the programmer with arrays (you still have to manually remember to use the accessor, not []), you also have to manually remember which pointers are pointers and which are arrays, and this representation doesn't work for pointing into subsections of an array (a similar problem to C-style strings), nor does it work well for putting arrays on the stack, which means one is forced to allocate every array (both of which mean the safe C is likely slower than the equivalent in Rust or even C++).

agree -- inability to do variable-sized arrays on the stack is the root of the problem.

I'm not even talking about variably sized arrays, just creating a statically sized one and passing it into functions that take dynamically-sized one. For instance, a read function that fills an existing buffer doesn't care if the buffer is on the heap or on the stack, it only cares that it doesn't overrun the bounds.

alloca-style variable arrays is a whole other can of worms of danger and complexity.

This is what I really like about Ada. Variable-sized arrays and structs on the stack is easy, safe, and efficient in Ada.

What do you mean? Variable-length arrays are OK in C.

oops -- you're right.

https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html

Legal in C99, available in C++ on gcc/clang.

Optional in C11, not accepted in ANSI C++17.

Not in C11, they were removed due to security issues and became an optional language feature.

I agree that having to remember is a problem, it's one of the many shortcomings of C that it doesn't let you differentiate between types at compile time.

Pointing into subsections works fine. You just have to create a type for it. This solution doesn't have the same problems as strings because you don't rely on a terminating entry, and it's what languages like Rust or Java do as well.

You can allocate dynamic arrays on the stack in C just fine with alloca(). The only performance cost is when checking bounds, but since it's a dynamic array, it's the same cost you'd pay in Rust.

Creating a type for it, for each type of array, will require exactly the macro array thing I was talking about. And see the sibling comment for how dynamic arrays/alloca isn't relevant, I'm just talking about static arrays. (Dynamic arrays on the stack do have a performance cost, as they get in the way of the compiler's optimiser/code generator: having non-fixed stack frames makes accessing locals annoying.)

Arrays and pointers in C already have that int. That's why sizeof() works. The issue is an extra if statement on every single array and pointer access.

They don't, sizeof is a compile-time constant. On a pointer, sizeof() just reports the size of the pointer itself (i.e. 4 or 8 bytes on most modern platforms), not the size of the data to which it points (and sizeof(*pointer) reports the size of the type to which pointer points, it doesn't know anything about how many values of that type are stored). For an array, the length is known statically (i.e. it's in the type), and so the computation can be done at compile time.

And this is such a misconception that it's often cited as a footgun: http://www.cplusplus.com/faq/sequences/arrays/sizeof-array/

> A beginner will often try something along the lines of size = sizeof( myarray ) (which is incorrect).

sizeof isn't always a compile-time constant: if it's applied to variably-modified type, it's not (obviously).

Oh, yes, I'd forgotten about VLAs... Compile-time constant, except for sometimes.

You're missing main glaring issue with parametric polymorphism, bloat.

While "unnecessary"/extra generated code is a trade-off one has to consider when choosing to use the specialize/monomorphise-everything implementation of parametric polymorphism (it isn't the only one), it isn't a problem in this case: the types themselves are a compile-time abstraction and don't exist at runtime, and the functions are all tiny (a branch, a memory access and a function call/abort).

Additionally, all the functions should be inlined anyway because the function call overhead will likely be as much or more than the actual code, and, more importantly, inlining enables other optimisations (removing the branch, vectorising the memory access, etc.). Once inlined, the code will be the same as the manual/macro-based approach of writing `if` statements around each array[index] access.

Reply on news.ycombinator.com