Collections-C, generic data structures for C • Hacker News Board

Re: Collections-C, generic data structures for C

#31

Post by seiji » Sun, Mar 13, 2016, 7:31 PM UTC

eps wrote: post #24

Nice, but it's rather naive and through that - needlessly wasteful. It's C. Why on Earth you'd want to allocate a separate list node for each piece of data when you can embed this node directly into the data and then use container_of or similar offsetof() derivative to get a pointer to the data by a pointer to a list item? Saves you at least sizeof(void*) per item and eliminates a chance of list_add ever failing amon…

allocate a separate list node for each piece of data

So many programmers don't even consider "overhead" of data when writing things. But, most of the time it doesn't matter. Do you need a list of ten things? Great. Do whatever. Do you need a list of a billion things? Then you need to rethink everything from the bottom up.

when all you need is just a pointer to realloc

Wrong! https://github.com/Tarsnap/libcperciva/commit/cabe5fca76f6c3...

Re: Collections-C, generic data structures for C

#32

Post by gibsjose » Sun, Mar 13, 2016, 7:43 PM UTC

rewqfdsa wrote: post #27

Honestly, why? Most of the time, you want to write C++, with exceptions, and the STL. You can make this kind of programming as robust as you want against memory allocation failure. If you don't want to use this style of programming, for whatever reason, check out sys/queue.h. It's already on your system, if you're using some kind of Unix.

If you are using an RTOS (which many timing-critical applications run on), you should be worried about memory allocations happening under the hood.

If you don't have full control over when memory is being allocated/reallocated, your system is now non-deterministic.

With pure C, you can know exactly when those few extra instructions for resizing your dynamic array are going to happen.

Re: Collections-C, generic data structures for C

#33

Post by [deleted] » Sun, Mar 13, 2016, 8:37 PM UTC

seiji wrote: post #31

eps wrote: post #24

Nice, but it's rather naive and through that - needlessly wasteful. It's C. Why on Earth you'd want to allocate a separate list node for each piece of data when you can embed this node directly into the data and then use container_of or similar offsetof() derivative to get a pointer to the data by a pointer to a list item? Saves you at least sizeof(void*) per item and eliminates a chance of list_add ever failing amon…

allocate a separate list node for each piece of data So many programmers don't even consider "overhead" of data when writing things. But, most of the time it doesn't matter. Do you need a list of ten things? Great. Do whatever. Do you need a list of a billion things? Then you need to rethink everything from the bottom up. when all you need is just a pointer to realloc Wrong! https://github.com/Tarsnap/libcperciva/com…

[deleted]

Re: Collections-C, generic data structures for C

#34

Post by catnaroek » Sun, Mar 13, 2016, 9:15 PM UTC

seiji wrote: post #31

eps wrote: post #24

Nice, but it's rather naive and through that - needlessly wasteful. It's C. Why on Earth you'd want to allocate a separate list node for each piece of data when you can embed this node directly into the data and then use container_of or similar offsetof() derivative to get a pointer to the data by a pointer to a list item? Saves you at least sizeof(void*) per item and eliminates a chance of list_add ever failing amon…

allocate a separate list node for each piece of data So many programmers don't even consider "overhead" of data when writing things. But, most of the time it doesn't matter. Do you need a list of ten things? Great. Do whatever. Do you need a list of a billion things? Then you need to rethink everything from the bottom up. when all you need is just a pointer to realloc Wrong! https://github.com/Tarsnap/libcperciva/com…

> So many programmers don't even consider "overhead" of data when writing things.

Because they're using managed languages where the amount of overhead per object can't be reduced to zero. And also because, in exchange for that overhead, they get other benefits, like compacting garbage collection. But you don't get this in C.

Re: Collections-C, generic data structures for C

#35

Post by catnaroek » Sun, Mar 13, 2016, 9:34 PM UTC

gibsjose wrote: post #32

rewqfdsa wrote: post #27

Honestly, why? Most of the time, you want to write C++, with exceptions, and the STL. You can make this kind of programming as robust as you want against memory allocation failure. If you don't want to use this style of programming, for whatever reason, check out sys/queue.h. It's already on your system, if you're using some kind of Unix.

If you are using an RTOS (which many timing-critical applications run on), you should be worried about memory allocations happening under the hood. If you don't have full control over when memory is being allocated/reallocated, your system is now non-deterministic. With pure C, you can know exactly when those few extra instructions for resizing your dynamic array are going to happen.

Same in C++. There's `std::vector::reserve`, which grows the vector's underlying physical buffer, without logically adding any new elements. If you `reserve` enough capacity before inserting anything, it's even a `O(1)` operation.

Re: Collections-C, generic data structures for C

#36

Post by deadgrey19 » Sun, Mar 13, 2016, 9:44 PM UTC

vc98mvco wrote: post #17

A quick look shows this is storing void* pointers only. My excitement was quickly over as I was expecting something with _Generic macros or ability to manage memory for any type. https://github.com/srdja/Collections-C/blob/master/src/hasht... shows the container is manually configurable. Look at the defines at the bottom. This would mean the container file source-header pair, would have to be duplicated for every typ…

Take a look at this instead. Work started on this before C-generics came about, so there is pretty heavy macro usage, but all data structures are type safe: https://github.com/mgrosvenor/libchaste

Re: Collections-C, generic data structures for C

#37

Post by deadgrey19 » Sun, Mar 13, 2016, 9:47 PM UTC

If you're interested in this sort of thing, take a look at https://github.com/mgrosvenor/libchaste. Work started on this before C-generics came about, so there is pretty heavy macro usage, but all data structures are type safe rather than the "cast to void*" approach which is common in this space. It's a bit less mature, but reasonably well covered by unit tests where it matters.

Re: Collections-C, generic data structures for C

#38

Post by srdja » Sun, Mar 13, 2016, 10:23 PM UTC

Hello everyone, I'm the author of this library. I was quite surprised to find it on the front page of HN! I must thank you for all the great feedback, it's been very helpful. I agree that it has rough edges and that it also lacks some useful features but I guess this is mostly because I was the only user of it.

I very much welcome your suggestions on how to make better and more useful. :)

Re: Collections-C, generic data structures for C

#39

Post by srdja » Sun, Mar 13, 2016, 10:28 PM UTC

wangchow wrote: post #3

Would be nice to have parallel structures like "Intel threading building blocks" provides. https://en.m.wikipedia.org/wiki/Threading_Building_Blocks I recommend this book to understand such structures: https://www.goodreads.com/book/show/14788830-structured-para...

I'll definitely look into it.

Re: Collections-C, generic data structures for C

#40

Post by vc98mvco » Sun, Mar 13, 2016, 10:32 PM UTC

deadgrey19 wrote: post #36

vc98mvco wrote: post #17

A quick look shows this is storing void* pointers only. My excitement was quickly over as I was expecting something with _Generic macros or ability to manage memory for any type. https://github.com/srdja/Collections-C/blob/master/src/hasht... shows the container is manually configurable. Look at the defines at the bottom. This would mean the container file source-header pair, would have to be duplicated for every typ…

Take a look at this instead. Work started on this before C-generics came about, so there is pretty heavy macro usage, but all data structures are type safe: https://github.com/mgrosvenor/libchaste

I see you use C macro templates. I have been experimenting with containers that use those. The advantages are speed and full type safety, and disadvantages are long compilations times (which have to be done only once though), the need to define a new template for every type in (only one) separate file, code bloat, and somewhat long function names (I don't use member function pointers).

I'm not sure if all that is worth it.