Hacktical C: practical hacker's guide to the C programming language

by signa11 • 1 year ago

218 176 1 year ago

akdev1l2• 1 year ago

Microsoft has unfortunately chosen to neglect C for a long time, its compilers dragging far behind the rest of the pack.

Is this still true? MSVC is pretty good at compiling C++ nowadays

chaosite• 1 year ago

MSVC always focused on C++, and C was treated as an afterthought.

pjmlp25• 1 year ago

The irony is that Microsoft was the very last MS-DOS compiler vendor to support C++ in their C tooling with Microsoft C/C++ 7 in 1992, that changed with the release of Visual C++ in 1993.

qsort• 1 year ago

I think he's referring to C specifically, not C++. It's true that modern versions of MSVC are compliant (and they're also typically faster at implementing features than gcc and clang), but for the longest time there were subtle differences in their C library. To this day I don't think they support VLAs, which are technically standard C (At least until recently, I'm not sure about the latest versions, hopefully someone more knowledgeable can say more).

akdev1l2• 1 year ago

I see. I kind of assumed improving the C++ compiler required improving the C parts as well.

VLA situation seems complex: https://stackoverflow.com/questions/55696680/in-which-versio...

DobarDabar• 1 year ago

Compare performance, features or anything of Clang and MSVC and you'll see the differences.

shakna• 1 year ago

For C (not C++), MSVC got C17 in 2020, apart from VLAs - which are never planned. No real roadmap for if/when it will get C23 - which is not just fully implemented in GCC, but the default used standard.

pjmlp25• 1 year ago

They are talking about C not C++, for Microsoft C was done, it was about time to move into C++.

This was the official position in 2012,

https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...

However after the Microsoft reboot with Satya, there was a change of heart regarding C, back in 2020, with C11 and C17 being supported,

https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...

And 2022

https://devblogs.microsoft.com/cppblog/c11-atomics-in-visual...

However there is no official roadmap regarding C23 support, and now with the whole safety discussion going on and Secure Future Initiative, probably will never happen.

Additionally clang is a blessed compiler at Microsoft, it is included on Visual Studio, so whatever MSVC doesn't support can be done in clang as alternative.

HexDecOctBin2• 1 year ago

They have added one feature (typeof) from C23, so maybe they will add the rest when they release C++26. Or maybe they won't. Microsoft is an expert in inflicting the cruelty of providing just enough hope.

camel-cdr• 1 year ago

Microsoft took 30 years to implement a C89 compatible preprocessor: https://docs.microsoft.com/en-us/cpp/preprocessor/preprocess...

lou13062• 1 year ago

Using a stricter language helps with reducing some classes of bugs, at the cost of reduced flexibility in expressing a solution and increased effort creating the software.

First of all, those languages do not "help" "reducing" some classes of bugs. They often entirely remove them.

Then, even assuming that any safe language with unsafe regions (Rust, C#, etc) would not give you comparable flexibility at a fraction of the risk... if your flexible, effortless solution contains entire classes of bugs, then there is no point in comparing "effort". You should at least take into account the effort in providing a software with a high confidence that those bugs are not there.

immibis2• 1 year ago

If the language has unsafe regions, it doesn't entirely remove classes of bugs, since they can still occur in unsafe regions.

(Predictable response: "But they can only occur in unsafe regions which you can grep for" and my response to that: "so?")

guappa• 1 year ago

Usually they can also happen outside, if you did something wrong in the unsafe region.

edit: I'm sorry that my captain obvious moment is turning out to be some truth bomb for some. Please keep downvoting as a way to regain your inner peace.

sjamaan• 1 year ago

I suppose the better response is that it removes those classes of bugs where they are absolutely unnecessary. Tricky code will always be tricky, but in the straightforward 80% (or more) of your code such bugs can be completely eliminated.

It's unfortunate that C has so many truly unnecessary bugs which are only caused by stupid overly "clever" exploitation of undefined behaviour by compilers.

lou13062• 1 year ago

No matter whether you are using C for "freedom" or "flexibility" of "power", 95% of the time you only need that in a very small portion of your codebase. You almost definitely do _not_ need any of that in, say, the logic to parse CLI arguments or config files, which however is a prime example of a place where vulnerabilities are known to happen.

oconnor6632• 1 year ago

Predictable response: "But they can only occur in unsafe regions which you can grep for" and my response to that: "so?"

The situation is both worse than this and better than this. Consider the .set_len() method on Rust's Vec. It's unsafe, because you could just .set_len(1_000_000) and then the Vec would happily let you try to read the nonexistent millionth element and segfault. However, if you could edit the standard library sources, you could add this new method to Vec without touching any unsafe code:

    pub fn set_len_totally_safe_i_promise(&mut self, new_len: usize) {
        self.len = new_len;
    }

This is exactly the same as the real set_len, except it's a "fn" instead of an "unsafe fn". Now the Vec API is totally broken, and safe callers can corrupt memory. Also critically, we didn't write any unsafe code in "set_len_totally_safe_i_promise". The key detail is that this new method has access to the private self.len field of Vec that unsafe blocks in the same module rely on.

In other words, grepping for all the unsafe blocks isn't sufficient for saying that a program is UB-free. You also have to make sure that none of the safe code ever violates an invariant that the unsafe blocks rely on. Read the comments, think really hard, etc.

So...what's the point of all this? The point is that it lets us define a notion of "soundness", such that if I only write safe code, and I only use libraries that are "sound", we can guarantee that my program is UB-free. In other words, any UB in my program would necessarily point to a bug in one of my dependencies, in the stdlib, or in the compiler. (Or you know, in the hardware, or in mathematics itself.) In other other words, instead of auditing my entire gigantic (safe) program for UB, we can reduce the problem to auditing my dependencies for soundness. Crucially, this decouples the difficulty of the problem from the size of my program. This wouldn't be very interesting if "safe code" was some impoverished subset, like "unsigned integer arithmetic only". But in fact safe code can use pointers, tagged unions, pointers into tagged unions, heap allocation/freeing, and multithreading. Lots of large, complicated, useful, real-world programs are written in 100% safe code. Here the version of this story with all the caveats and footnotes: https://jacko.io/safety_and_soundness.html

agentultra3• 1 year ago

No amount of chest-thumping about how good of a programmer you are and telling everyone else to, "get good," has had any effect on the rate of CVE's cause by memory safety bugs that are trivial to introduce in a C program.

There are good reasons to use C. It's best to approach it with a clear mind and a practical understanding of its limitations. Be prepared to mitigate those short comings. It's no small task!

uecker8• 1 year ago

I am not sure the number of CVEs measures anything meaningful. The price for zero-days for important targets goes into the millions.

While I am sure there can not be enough security, I am not at all sure the extreme focus on memory safety is worth it, and I am also not sure the added complexity of Rust is really worth it. I would prefer to simplify the stack and make C safer.

codr724• 1 year ago

Definitely, but the idea is that its unique feature set is worth it.

codr724• 1 year ago

So use Rust, fine by me.

I might too some day, who knows.

throwaway78942• 1 year ago

  #define hc_task_yield(task)   
  do {     
    task->state = __LINE__;   
    return;     
    case __LINE__:;           
  } while (0)

That's just diabolical. I would not have thought to write "case __LINE__". In the case of a macro, using __LINE__ twice expands to the same value where the macro is used, even if the macro has newlines. It makes sense, but TIL.

veltas• 1 year ago

Credit to Simon Tatham

https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

makeset• 1 year ago

I knew the name sounded familiar:

Simon Tatham's Portable Puzzle Collection https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

quietbritishjim4• 1 year ago

no commonly used high level language supports the coroutine call primitive

Shows how old this post is. In fact I remember reading it well over 10 years ago, maybe more like 20. archive.org says that it's at least as old as 2001. A great article.

I'm very excited to see he's published a new article on C++20 coroutines. I've read (or maybe skimmed...) a few introductions and not really got them, despite having used C# and Python coroutines a lot with no problems (even making changes to an async runtime for Python). Given how clear his C coroutine article is, I'm optimistic about the C++ article.

So, after the course, I went away and studied on my own, and wrote the introduction to C++ coroutines that I’d have liked to see.

https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/corou...

HeliumHydride• 1 year ago

With GNU extensions, you can make a simpler coroutine macro without switch/case abuse:

    #define CO_BEGIN static void* cr_state_ = &&cr_st_0; goto *cr_state_; cr_st_0:
    #define CO_RETURN(x) ({ __label__ resume; cr_state_ = &&resume; return (x); resume:; })

gthompson512• 1 year ago

Minor correction, macros CANT have newlines, you need to splice them during preprocessing using \ followed by a new line, the actual code has these:

from https://github.com/codr7/hacktical-c/blob/main/macro/macro.h

#define hc_align(base, size) ({ \ __auto_type _base = base; \ __auto_type _size = hc_min((size), _Alignof(max_align_t)); \ (_base) + _size - ((ptrdiff_t)(_base)) % _size; \ }) \

After preprocessing it is a single line.

fuhsnn• 1 year ago

We might get multi-line macros in C2y standard: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3524.txt

tanelpoder• 1 year ago

I've written C on-and-off for over 30 years (just various throw-away prototypes and OS/app interaction microbenchmarks) and it took a while + a web search to get it. Diabolical indeed. Edit: And makes sense in hindsight.

pjmlp25• 1 year ago

The reason I believe C is and always will be important is that it stands in a class of its own as a mostly portable assembler language, offering similar levels of freedom.

When your computer is a PDP-11, otherwise it is a high level systems language like any other.

pornel2• 1 year ago

Less controversially, when you write C, you write for a virtual machine described by the C spec, not your actual hardware.

Your C optimizer is emulating that VM when performing symbolic execution, and the compiler backend is cross-compiling from it. It's an abstract hardware that doesn't have signed overflow, has a hidden extra bit for every byte of memory that says whether it's initialized or not, etc.

Assembly-level languages let you write your own calling conventions, arrange the stack how you want, and don't make padding bytes in structs cursed.

aninteger• 1 year ago

Less controversially, when you write C, you write for a virtual machine described by the C spec, not your actual hardware.

Isn't this true for most higher level languages as well? C++ for instance builds on top of C and many languages call into and out of C based libraries. Go might be slightly different as it is interacting with slightly less C code (especially if you avoid CGO).

bmandale• 1 year ago

These are all such nonsensical misinterpretations of what people mean when they say C is "low level". You absolutely don't write C for the C abstract machine, because the C spec says nothing about performance, whereas performance is one of the primary reasons people write C.

The existence of undefined behaviour isn't proof that there is a C "virtual machine" that code is being run on. Undefined behaviour is a relaxation of requirements on the compiler. The C abstract machine doesn't not have signed overflow, rather it allows the compiler to do what it likes when signed overflow is encountered. This is originally a concession to portability, since the common saying is not that C is close to assembly, but rather that it is "portable" assembler. It is kept around because it benefits performance, which is again one of the primary reasons people write C.

grandempire9• 1 year ago

Which other popular language more accurately represents a random access machine of fixed word length?

alexvitkov2• 1 year ago

None, but that'a not what computers are. C assumes that in a few places, e.g. variadic functions, and those are the worst parts of the language.

pjmlp25• 1 year ago

I don't know, Ada, Modula-2, Object Pascal, PL/I, NEWP, PL.8, D, Zig, Mesa, ATS,....

But then again, you booby trapped the question with popular language.

kryptiskt2• 1 year ago

C lacks sympathy with nearly all additions to hardware capabilities since the late 80s. And it's only with the addition of atomics that it earns the qualification of "nearly". The only thing that makes it appear as lower level than other languages is the lack of high-level abstraction capabilities, not any special affinity for the hardware.

For one, would expect that a low level language wouldn't be so completely worthless at bit twiddling. Another thing, if C is so low level, why can't I define a new calling convention optimized for my use case? Why doesn't C have a rich library for working with SIMD types that has been ubiquitous in processors for 25 years?

NoTeslaThrow2• 1 year ago

When your computer is a PDP-11, otherwise it is a high level systems language like any other.

Describing C as "high-level" seems like deliberate abuse of the term. The virtual machine abstraction doesn't imply any benefits to the developer.

pjmlp25• 1 year ago

Neither does pretending C is a macro Assembler.

timClicks• 1 year ago

That's a curious remark, although I guess it doesn't look high level from the eyes of someone looking at programming languages today.

C has always been classed as a high level language since its inception. That term's meaning has shifted though. When C was created, it wasn't assembly (middle) or directly writing CPU op codes in binary/hex (low level).

ecb_penguin• 1 year ago

Describing C as "high-level" seems like deliberate abuse of the term

Honestly it doesn't really matter. High level and low level are relative to each-other (and machine language), and nothing changes based on what label you use.

Best thing to do is shrug and say "ok".

ryao17• 1 year ago

Spend 90 days writing nothing but assembly language and then tell me that you believe C is a low level language.

hgs3• 1 year ago

Can you elaborate? C constructs generally map to one or a few assembly instructions at most. You can easily look at C and predict the generated assembly. This is in contrast to other compiled languages, like Go, that inject instructions for garbage collection and other runtime features.

pjmlp25• 1 year ago

See my list of languages on a sibling thread, same applies to those, nothing special about C there.

uecker8• 1 year ago

While C was adapted to the PDP-11, this was adding byte-level memory access. Otherwise I do no think there is anything in C specific to the PDP-11, or what would this be?

What makes C low-level is that it can work directly with the representation of objects in memory. This has nothing to do with CPU features, but with direct interoperability with other components of a system. And this is what C can do better than any other language: solve problems by being a part of a more complex system.

WalterBright• 1 year ago

The post-increment and post-decrement operators mapped directly onto PDP-11 CPU addressing modes.

The integral promotion rules come directly from the PDP-11 CPU instruction set.

If I recall correctly so does the float->double promotions.

CPUs started adapting to C semantics around the mid-80's. CPU designers would profile C generated code and change to be able to more efficiently run it.

codr724• 1 year ago

Yeah, people keep repeating that like a broken record lately, it smells like Rust to me.

No one is claiming it was built for today's processors, just that it puts less obstacles between you and the hardware than almost any other language. Assembler and Forth being the two I'm familiar with.

pjmlp25• 1 year ago

Because people keep repeating the urban myth of portable assembler and being the very first systems programming language.

One of the very first systems programming languages was JOVIAL, from 1958. C's inventors were still finalising their studies.

_kst_• 1 year ago

C is a relatively low level language, but it is not assembly language.

The difference is clear. Assembly language programs specify sequences of CPU instructions. C programs specify runtime behavior.

9d• 1 year ago

C doesn't try to save you from making mistakes. It has very few opinions about your code and happily assumes that you know exactly what you're doing. Freedom with responsibility.

I love C because it doesn't make my life very inconvenient to protect me from stubbing my toe in it. I hate C when I stub my toe in it.

OCASMv27• 1 year ago

No, it just makes it inconvenient to try to protect yourself from stubbing your toe in it.

codr724• 1 year ago

C doesn't make anything inconvenient, that's its major appeal. Some things are convenient by design, yes, but it's not trying to prevent you from doing anything. That's a feature.

neonsunset• 1 year ago

Usually stubbing your toe does not take your whole leg.

0xEF• 1 year ago

I've heard it put another way that I enjoyed: "C assumes you know what you're doing, which is only a problem if you don't know what you're doing."

tialaramex6• 1 year ago

Having spent many, many years paid to write C, and with no wish to write any more now than I learned Rust, I would suggest a rewording:

"C assumes you know what you're doing, which is only a problem because you don't know what you're doing."

Periodically, especially in r/cpp I run into people who are apparently faultless and so don't make the mistakes that make these languages dangerous, weirdly none of these people seem to have written any software I can inspect to see for myself what that looks like, and furthermore the universe I live in doesn't seem to have any of the resulting software. I choose to interpret this mystery as: People are idiots and liars, but of course there could be other interpretations.

codr724• 1 year ago

Oh, very much likewise, but there's always two sides to a coin.

oconnor6632• 1 year ago

It has very few opinions about your code

I understand where this is coming from, but I think this is less true than it used to be, and (for that reason) it often devolves into arguments about whether the C standard is the actual source of truth for what you're "really" allowed to do in C. For example, the standard says I must never:

- cast a `struct Foo*` into a `struct Bar*` and access the Foo through it (in practice we teach this as the "strict aliasing" rules, and that's how all(?) compilers implement it, but that's not what §6.5 paragraph 7 of the standard says!)

- allow a signed integer to overflow

- pass a NULL pointer to memcpy, even if the length is zero

- read an unitialized object, even if I "don't care" what value I get

- read and write a value from different threads without locking or atomics, even if I know exactly what instructions those reads and writes compile into and the ISA manual says it's 100% fine to do that

All of these are ways that (modern, standard) C doesn't really "do what the programmer said". A lot of big real-world projects build with flags like -fno-strict-aliasing, so that they can get away with doing these things even though the standard says they shouldn't. But then, are they really writing C or "C with custom extensions"? When we compare C to other languages, whose extensions are we talking about?

ryao17• 1 year ago

  cast a `struct Foo*` into a `struct Bar*` and access the Foo through it (in practice we teach this as the "strict aliasing" rules, and that's how all(?) compilers implement it, but that's not what §6.5 paragraph 7 of the standard says!)

Use the union type. Abusing it for aliasing violates the standard too, but GCC and Clang implement an extension that permits this. Alternatively, just allocate a char array and cast it as you please. Strict aliasing does not apply to char arrays if I recall.

  allow a signed integer to overflow

Is this still true? I thought that the reason for this is because C left the implementation to define how signed arithmetic worked, meaning you could not assume two’s complement, but the most recent C standard was supposed to mandate two’s complement.

  pass a NULL pointer to memcpy, even if the length is zero

There is a reason for this. memcpy is allowed to start reading early as a performance optimization, before it does a branch that checks if reading is only. I do wonder what happens if you only want to copy 1 byte and that byte has invalid memory right next to it. Presumably, this optimization would read more than a byte.

  read an unitialized object, even if I "don't care" what value I get

You are probably doing something wrong if you do this. It is not even good as an entropy source.

  read and write a value from different threads without locking or atomics, even if I know exactly what instructions those reads and writes compile into and the ISA manual says it's 100% fine to do that

Earlier C standards likely did not say anything about this because they did not support multithreading, but outside of possibly reading/writing to hardware registers, you do not want to do this because of races. Even if you think you know better, you almost certainly do not.

throwaway78942• 1 year ago

As someone who has a file with similar hacks, I will say this: I am not a C++ fan, but if you find yourself writing C code where you simulate methods via structs with function pointers often, just use C++ as a basic "C with classes" at that point. You want methods anyway, you have to go through a pointer dereference to call the function, it's just not worth the code weirdness. If you have the grit to use structs with function pointers everywhere, you have the grit to stick to the simpler subset of C++.

uecker8• 1 year ago

Why? I do not find the syntactic sugar C++ adds very helpful and it misses other C features.

ryao17• 1 year ago

Perhaps he wants to jump through hoops to avoid function pointers, even when doing that in C++ for optional functions like is done in the VFS requires gymnastics:

https://godbolt.org/z/4GWdvsz6z

That is the closest I can get it to implementing an optional function via a C++ class member function instead of a function pointer. It is not only insane, but also masochistic in comparison to how it would be done via function pointers:

https://godbolt.org/z/qG3v5zcYc

unclad59682• 1 year ago

I'm torn. The step from C to any c++ is big. Now if you want anybody to be able to use your code they need to be using c++ or you have to provide a C api anyway. On the other hand, manually implementing vtables is annoying. Ive been sticking to pure C and haven't been bothered enough to go back to any c++ yet (about 6 months on my current project). I mostly only miss templated containers so far.

ryao17• 1 year ago

It is more annoying to want to implement an optional function in a class and then have no simple way to check if that optional function is implemented in the object without, having to edit code that guards the call sites every time you add a derived class that implements it, or having to implement your own way of querying the object to know if it is supported.

codr724• 1 year ago

Nope, not from my experience.

Because in C++ the features are just there right around the corner, they will seep into the code base.

And I don't want even classes, there's too much junk in there that I don't need.

ryao17• 1 year ago

Can you think of anything I missed:

https://news.ycombinator.com/item?id=43701516

ryao17• 1 year ago

This is very bad advice for a few reasons:

1. It is not possible to add optional member functions (which would be pure virtual functions) to a C++ class base class and then check at runtime if they are unimplemented in the object (at least not without implementing some way to query the object, which is slow). If you say to handle this by having typeid checks at runtime, look at the VFS and then notice that you cannot implement this typeid check in advance, since you cannot add a typeid check for a derived class that did not even exist when you compiled your code. Thus, you still need to use structs of function pointers in C++. Maybe you can use C++ classes for some cases where structs of function pointers are used, but you would giving up the ability to implement optional functions in a sane way.

2. It ignores all of the things in C that are absent from C++. In particular, C++ refuses to support C’s variably modified types and variable length arrays, which are useful language features.

3. It ignores all of the things in C++ that you likely do not want, such as exceptions and RTTI. The requirement to typecast whenever you assign a void pointer to any other pointer is also ridiculous.

humanrebar2• 1 year ago

You can do everything you describe in C++. Even the language features are available (or diableable) as compilation flags.

pjmlp25• 1 year ago

1. There are other approaches to this with templates and concepts, and as added bonus, stronger type checking.

Thankfully regarding 2., Google went the extra mile to pay for removing them from the Linux kernel, and they were made optional C11 onwards exactly because they are an attack vector.

3. It is called stronger type safety, ridiculous is the C community still approaching computers as if writing K&R C.

jstimpfle• 1 year ago

There's a big issue with C++ classes -- or rather methods. You need to list the entire class definition to expose public methods. That includes private members and private methods. This breaks encapsulation, exposing implementation details and their dependencies in the public header. This in turn leads to looong compile times and needless recompilations.

pjmlp25• 1 year ago

Hence modules, and yes I know there are still some issues to sort out.

steinuil• 1 year ago

Some points about the introduction, but otherwise this seems like an interesting collection of (slightly deranged?) patterns in C.

The truth is that any reasonably complicated software system created by humans will have bugs, regardless of what technology was used to create it.

"Drivers wearing seatbelts still die in car accidents and in some cases seatbelts prevent drivers from getting out of the wreckage so we're better off without them." This is cope.

Using a stricter language helps with reducing some classes of bugs, at the cost of reduced flexibility in expressing a solution and increased effort creating the software.

...and a much smaller effort debugging the software. A logic error is much easier to reason about than memory corruption or race condition on shared memory. The time you spend designing your system and handling the errors upfront pays dividends later when you get the inevitable errors.

I'm not saying that all software should be rewritten in memory-safe languages, but I'd rather those who choose to use the only language where this kind of errors regularly happens be honest about it.

codr724• 1 year ago

Debugging from specific classes of bugs, yes.

I'm not trying to hide anything, just help shift the balance back to common sense.

_false• 1 year ago

Honest q: after skimming through the book it's unclear how it's targeted towards hackers (c.f. academics)?

codr724• 1 year ago

Defined as practical, curious problem solvers, I'm aware the word has other interpretations.

talles• 1 year ago

Any quick way to make a PDF out of this?

theiasson• 1 year ago

You'll need pandoc and xelatex

  $ pandoc --pdf-engine=xelatex --toc README.md {macro,fix,list,task,malloc1,vector,error,set,malloc2,dynamic,stream1,slog}/README.md -o book.pdf

teo_zero• 1 year ago

Beware that the second section about fixed-point arithmetic is actually about floating point with exponent in base 10.

Besides, the operations are all wrong and only work for trivial values of the exponents, like 0, 1 and 2.

Calwestjobs• 1 year ago

"These days; many programmers will recommend choosing a stricter language, regardless of the problem being solved. Most of those programmers wouldn't trust themselves with the kind of freedom C offers, many haven't even bothered to learn the language properly."

Same thing people said about other people not compiling by hand lol.

hresvelgr• 1 year ago

The people I've met who have made similar remarks about C have authored some of the most heinous pointer tomfoolery I've ever seen in my life. It's a remark indicative of a hubris that has remained unchecked or worse, in denial.

codr724• 1 year ago

So you couldn't understand their code, and therefore everyone who says the same things is incompetent and in denial. That's one way to explain the experience you had.

siev• 1 year ago

I like the sentiment, I love C. But this book seems riddled with errors and baffling decisions.

First of all, the fixed points are LITERALLY NOT FIXED POINTS. They're decimal floats. Fixed points are just integers that re-scale when multiplied or divided. There is no exponent field, no nothing. The author seems to have confused the notion "fixed points allow for precise calculations of monetary values" to mean that they're decimal. They're not. That section of the book contradicts itself constantly and also the code is wrong.

Also an ordered vector is used to implement a map/set. Because:

Most people would likely instinctively reach for hash tables, and typically spend the next few months researching optimal hash algorithms and table designs.
A binary searched vector is as simple as it gets and performs pretty well while being more predictable.

A basic hash table or hash set[1] is both simpler and faster than this solution. And I don't see what's stopping someone from spending the next few months researching optimal dynamic array growth and searching algorithms instead. This line of reasoning just doesn't make any sense.

And "Once nice advantage is that since they don't need any infrastructure, they're comparably cheap to create." What? It needs a dynamic array!

[1] https://github.com/skeeto/scratch/tree/master/set32

exceptione• 1 year ago

Thanks for sparing us bad information.

What would you recommend as a source instead?

codr724• 1 year ago

Thanks for sharing your opinions, I don't agree.

chipsa• 1 year ago

The fact you don’t agree is immaterial to the fact that your “fixed point” code doesn’t implement fixed point arithmetic. Fixed point arithmetic has a fixed scale factor for the type, not a value dependent scale factor.

tialaramex6• 1 year ago

Oh wow, yeah, that's not a fixed point type, it's a bad decimal type, code which uses this type is more likely to be faulty. If you can afford 64-bit integers, just work in pennies (cents, whatever) everywhere and don't sweat it.

The growable array type ("vector" following C++ parlance) lacks the bifurcated reservation API meaning it has the same problem as Bjarne's std::vector - but it's 2025 people, just because C++ made this mistake last century doesn't mean you need to copy them.

And finally yes you want a really good general purpose hash table, this is one of the places where generics shine most brightly, don't "spend the next few months researching" pick a language which does a decent job of this out of the box, but since you're in C, your utility library should likewise provide a decent hash table out of the box.

Swiss Tables are literally just a single growable allocation, this idea that you've somehow made your thing cheaper than a hash table by using the growable array type underneath it means you're at best four decades behind the state of the art, which is a bad sign.

This is a Young Discipline. David Musser's "Introspective sorting" paper was written after I learned sorting at University. Literally the class where they taught me about sorting was held before that paper was even written, let alone widely disseminated. The whole terminology of "Lock free" versus "Wait free" again, that's newer than my undergraduate final project on distributed systems. Because this is a Young Discipline it's crucial to go check, hey, the stuff I learned in class years ago, is that actually still correct, and does my understanding match reality - or am I about to recite a known falsehood because I forgot how time works and/or I didn't pay attention in class?

badmintonbaseba• 1 year ago

The growable array type ("vector" following C++ parlance) lacks the bifurcated reservation API meaning it has the same problem as Bjarne's std::vector - but it's 2025 people, just because C++ made this mistake last century doesn't mean you need to copy them.

What's "the bifurcated reservation API"?

nesarkvechnep• 1 year ago

Unpopular opinion but the BSDs are better OS for learning and hacking C. Super stable, amazing documentation, predictable, nice libraries included.

Hacktical C: practical hacker's guide to the C programming language

Related Stories