Hacker News Reader

Comment by glouwbug | Hacker News Reader

I backported a handful of C++ STL containers to ISO C99 to exemplify that a subset of C++, namely C with Templates, is a highly usable type-safe feature within the realm of ISO C99.

Included are a couple examples, like a JSON parser and a simple 6502 compiler. I have also written a small wiki, that showcases how to use the included containers: https://github.com/glouw/ctl/wiki

View on HN

This looks cool, but I dislike the naming. Calling a queue "queue" would be so much more readable than "que", and so on. I think the everything-is-three-letters gimmick is overall a drawback. Also, would it really hurt that much to write "#define PRIMITIVE" instead of "#define P"?

I've found that in forums like this, people generally react badly to comments about naming, but I've found that it actually matters more than people think it does.

Many things have exactly one correctly spelled full name, but many alternative contractions or cute variations.

Programmers can be expected to know the correct spelling of "vector" or "dequeue". They can't be expected to know your specific contraction or abbreviation of it. They can't guess and they're not mind readers. They have a muscle memory that has them type out the full word automatically, without thinking.

Don't break these expectations.

I mostly agree with this comment except “dequeue” is a bad example. C++ has called this data structure “deque” (pronounced deck) since the beginning of the STL. Is there another language/library that spells it dequeue?

> Is there another language/library that spells it dequeue?

Yes.

  https://www.npmjs.com/package/dequeue
  https://api.jquery.com/dequeue/
  https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.queue-1.dequeue?view=net-5.0

.NET uses Dequeue as a verb, not a noun though.

Perhaps that's another reason to call the data structure a "Deque" since "Dequeue" is already used for the verb meaning "to remove an item from a queue."

It's also for a completely different purpose, but I was answering about the spelling as a direct answer to a question.

For better or worse, Rust calls it a VecDeque, but I think this is meant to clarify that the structure is just Vec storage with some extra methods on top to provide convenient ring buffer usage patterns:

https://doc.rust-lang.org/std/collections/struct.VecDeque.ht...

https://docs.oracle.com/javase/7/docs/api/java/util/Deque.ht...

Common Lisp is a truly awful offender in this regard, with "cute" slightly-abbreviated opaque names for subtly-varying concepts.

EQ/EQL/EQUAL/EQUALP, PROCLAIM/DECLAIM/DECLARE, and the atrocious PAIRLIS (really??). And not to mention the fact that PAIRLIS returns an association list, which is entirely different from a "plist".

And then of course CAR, CDR, CADR, CDDR, et alia.

This is all second nature for an experienced Lisp programmer, but it makes for a difficult learning experience.

You are correct. But more important is internal consistency - and adherence to the consistency rules of the eco-system. This allows to deduce naming of API-Elements after a while. So the most important rule is- do not be creative. Think like a bureaucrat, adhere to the standards and the ecosystem around you.

I hate this field so much. That anyone creative chooses willingly to go into software is a miracle. Are there people out their with pre-broken spirits, that want to join this soul-less galley of horrors? Starvation should be preferable to this. But i digress..

Why not make naming something that can be personalized? Make the variablename a sort of rule-based-building-block-lego-system, that can be adapted by the user.

Increment+Variable -> "upIndex" for you Increment+Variable -> "incVar" for me. Everyone is happy, the frameworks and apis only specify the buildingblocks as variableNames.. autotranslated variableNames, customized to everyones flavour.

Hooray, i contributed. Prolonging the nightmare.

I've had the opposite complaints on my similar but verbose library. Some want short names and some want full explicit names.

I'm not sure which way is more popular. Paul Graham has mentioned in several essays how programmers are lazy and want to type the minimum number of characters possible. On the other hand Elon Musk has loudly complained about acronyms and contractions.

In the end you can't please everyone, so the developer just has to pick a style and go with it. If you dislike the short names, it's easy enough to put a comment above the template instantiation explaining what's going on.

I mean, one can (and I will argue "should", though I appreciate many people will be angry about this) used macros to change the names to whatever they want... but this makes a lot more sense if libraries stick with full names and the contractions are house style.

I think a lot of this has to do with what people develop with. If they are a vim person then typing long names is annoying, but if they use any type of IDE, the autocomplete removes that hassle and the benefits of having a clearer naming convention can shine.

In case anyone reading doesn't realize, Vim can do keyword completions. It isn't automatic, but out of the box, you can press ctrl+n to move through a list of possible completions.

Not as elegant as some IDEs I'm sure, but if typing is stopping you from using longer names, this could help.

Also, for IDE style completion:

https://github.com/ycm-core/YouCompleteMe

People confuse 'verbose' and 'clear'. Long names make my eyes glaze over as a reader.

Vim has autocomplete too. This is not an argument about vim since I have seen vim users employing both conventions.

Graham seems like he'd be much more authoritative on this topic than Musk.

I think in this case it’s largely a matter of taste. I actually like the everything is three letters thing. It feels clean, and personally I can still read and understand each abbreviation.

I do actually agree on the primitive vs p thing though...

The three-letter names have the advantage that it makes the function names shorter since they are prefixed with the same letters.

Another advantage of #define PRIMITIVE - it doesn't steal a handy 1-char identifier that the consuming program might want to use for its own purposes. And as well as making a longer identifier, I'd also personally suggest also adding a library-specific prefix, to further reduce the risk of conflicts.

(I have worked on code where the debug print macro was called P...)

This is cool! I've seen this C-with-templates used in the past with ".X" headers but haven't used the technique myself. Having something based on STL might help people to center on one library instead of constantly reinventing collections in C (which I've also done for some structures, and open sourced though I don't recommend using it: https://github.com/nitrogenlogic/nlutils).

I recall a few years back doing something like this implementing a binary heap just as a hobby project (https://github.com/Equationist/ctl/blob/master/pqueue.h). I was curious to see how unoptimized it was vis a vis the STL, and ran compiled equivalent test code for both my priority queue and the STL's C++ implementation, with just integers. I was kind of shocked to find that my implementation was like 30% faster when both were compiled at -O3 levels. Seeing this backport I guess there isn't anything fancy in the STL implementations, so it's less surprising that my naive implementation could be just as fast (or happen to be faster).

There's this theory that humans are antennas, and that we pick up "wavelengths from above" to build and create the world we live in. Not only did we decide on the same project name and idea, but we also used the same pre-processor hacks. How surreal.

As for your pqueue implementation, the efficacy of an optimizing compiler lies in the inherent complexity of the language. I can imagine the optimization backend for gcc is simpler (and more effective) than g++, but I am not an expert on compiler internals.

Where have you heard that theory? I've wondered about it myself, but other than some songwriter-specific conversation, I'm not sure I'm familiar with other people talking about it, and I'd like to be.

I'm not sure where I heard it, but if you are interested in an article: https://www.sciencedaily.com/releases/2014/01/140116085105.h...

It sounds somewhat similar to Sheldrake's morphic resonance ideas.

In other words, it's 100% BS; in Sheldrake's case, wholly contradicted by his own examples.

gcc and g++ use the same backend.

These kinds of macro hacks are pretty widespread, aren't they? To me, klib and its khash hash table is the most well-known implementation, see: https://github.com/attractivechaos/klib

And I've written similar things myself (hash table and vectors).

Its more likely that humans are redundant. That is, it is probable in a field of millions that two people come up with the same idea and implementation. I think the birthday paradox is a similar corollary on a smaller scale.

https://en.wikipedia.org/wiki/Birthday_problem

FreePascal has a lot of containers, perhaps more than the STL, but they all suck

I wanted a good hash map, so I spend a lot of time comparing them. There are like 10 separate map implementation in FreePascal, but they are all slower than C++'s std::unordered_map.

Then I compared another dozen of libraries, and found the fastest one that is like 50% faster than std::unordered_map. But it was a rather straight forward implementation of non-linear open addressing.

Did you consider using more traditional macros like VEC_ADD which works for all types rather than generating e.g. vec_<type>_add? The latter approach doesn't work with cscope and ctags, which is a pretty big drawback in my book (I like it when my super trivial IDE configuration works, which is only possible with C).

See the comment and following 4 macros for how this would work with a (add-only, not growable) hashmap:

https://github.com/matvore/nusort/blob/master/src/util.h#L16...

Well, that is how BIDS 1.0 was designed, before C++ got templates.

This is awesome! Very useful for writing highly portable software in C. I think I’ll use this library also with my students.

This along with Cosmopolitan libc which was recently posted here[1], would be awesome for writing tiny cross platform utilities in C.

[1]: https://news.ycombinator.com/item?id=25556286

Nice, very nice. All of it. Long live C.

Being stuck with C++ I did something in reverse - ported C-style ("intrusive") containers to ++, making them a bit safer to use, but keeping the syntax nearly the same.

https://github.com/apankrat/notes/tree/master/intrusive-cont...

The Boost libraries have an intrusive containers library, described here:

https://www.boost.org/doc/libs/1_75_0/doc/html/intrusive.htm...

Have you considered it? Is it deficient for your use case?

The post I linked to mentions it explicitly.

but it doesn't mention why not to use it.

It does, in the exact same sentence.

You mean this:

"the goal here is to make a better version of C-style containers rather than to implement something C++-style and similar,"?

But a goal is not a reason. I.e. why doing

  CONTAINER_OF( user_data, vip );

instead of

  container_of<&user_data::vip> vip_list;

is preferable? How are they even meaningfully different?

The reason is that the goal is not achievable using boost contraptions. At the very least it's not possible to use boost version without inheritance.

As to why to do what you wrote I have no idea. These two code snippets are unrelated.

of course it is possible to use boost intrusive without inheritance: it supports both hooks as base and hooks as members.

Oh, well, good for it.

If I were to pick the reason, it'd be simply that I don't like Boost.

To me, Boost is an ultimate embodiment of all that went wrong with C++ when it evolved from being a better version of C into the multi-paradigm monstrosity that it is now. Just look at the man page linked above. How to get a clever little concept of intrusive containers and completely decimate it into a technically correct, but unpalatable formulistic piece of engineering that, above all else, is rid of any shred of elegance that made the original concept so great in the first place.

Here's a stupid question: what's the difference of using an intrusive container against using an STL container of (probably smart) pointers? i.e. std::list<My class*>. I've done that plenty of times in my codes in the past.

Adding/removing items to std::list will result in extra allocations/deallocations.

It will also take up more space, to store that very pointer.

All of which starts to matter (a lot) when operating with very large data sets.

An intrusive node has a getter for the next intrusive node. And the data structure would use that getter to organize the elements of the data structure.

Among other implications (different memory locality and allocation guarantees), you could have the same intrusive node object used in several container objects or even classes (though not at the same time). That is, pull an element from a doubly linked list and insert it into a binary tree without reallocation.

With intrusive you can remove from the list in constant time from the object itself.

With std::list you need to find the iterate to the node before you can delete it.

What do you think about Glib?

Are they fuzzed? Should be useful as some guarantee against memory-safety bugs. Didn't find this mentioned in the project.

I have a series of functional tests in `tests/func` which randomly call container functions and check their output against the C++ STL. These tests run on every push, on all optimization settings, with and without gcc's address sanitizer.

Great work! And thank you for making it available for everyone.

Did you also run tests against other libraries such as glib?

Reply on news.ycombinator.com