HNHacker News
TopNewBestAskShowJobs

el_pollo_diablo

132 karma · joined November 30, 2023

submissionscomments
el_pollo_diablo··on I write type-safe generic data structures in C
Sure, but it is also very common for C programs to contain data structures that have one use in the program, and could still be instances of a generic type. You mentioned red black trees, which are a perfect example of that.
el_pollo_diablo··on I write type-safe generic data structures in C
If, by "situation", you mean the development of a small program with so many constraints that using existing libraries is out if the question, then yes.

Otherwise, that seems unwise to me. Not every user of a generic type has to be generic. A major selling point of generic types is that you write a library once, then everyone can instantiate it. Even if that is the only instance they need in their use case, you have saved them the trouble of reinventing the wheel.

No colleague of mine may need 10 different instances of any of my generic libraries, but I bet that all of them combined do, and that our bosses are happy that we don't have to debug and maintain 10+ different implementations.

el_pollo_diablo··on I write type-safe generic data structures in C
Sure, but your alternative code incorrectly assigns to (list)->payload. You have many other options. Without typeof, you can if(0) the assignment, or check type compatibility with a ternary operator like 1 ? (item) : (list)->payload and pass that to _list_prepend, etc. With typeof, you can store item in a temporary variable with the same type as (list)->payload, or build a compound literal (typeof(*(list))){.payload=(item)}, etc.
el_pollo_diablo··on I write type-safe generic data structures in C
This is about a function definition, not a random function declarator. C23 does not change anything in that case.
el_pollo_diablo··on I write type-safe generic data structures in C
C23 does not change anything in this situation, because we are talking about the definition of main(), not a forward declaration. More details here:

https://news.ycombinator.com/item?id=38729278#38732366

el_pollo_diablo··on Low-Level Optimization with Zig
Sure, that sort of language-specific idiosyncrasy must be dealt with in the compiler's front-end. In TFA's C example, consider that their loop

  while (i <= x) {
      // ...
  }
just needs a slight transformation to

  while (1) {
      if (i > x)
          break;
      // ...
  }
and C11's special permission does not apply any more since the controlling expression has become constant.

Analyzes and optimizations in compiler backends often normalize those two loops to a common representation (e.g. control-flow graph) at some point, so whatever treatment that sees them differently must happen early on.

el_pollo_diablo··on Low-Level Optimization with Zig
> In fact, even state-of-art compilers will break language specifications (Clang assumes that all loops without side effects will terminate).

I don't doubt that compilers occasionally break language specs, but in that case Clang is correct, at least for C11 and later. From C11:

> An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate.

el_pollo_diablo··on The SeL4 Microkernel: An Introduction [pdf]
> seL4 is the only microkernel that has a proof of correctness

ProvenCore (https://provenrun.com/provencore/) has a proof that covers correctness (memory safety, and more generally absence of UB, termination, etc.), functional properties (e.g. the fork() system call is a refinement of an abstract "clone" operation of abstract machines), and security properties (memory isolation).

el_pollo_diablo··on A marriage proposal spoken in office jargon
My comment was meant as a joke, given the context. I am familiar with these interjections, even as a non-native anglophone. Sorry for the time you took to write a good reply.
el_pollo_diablo··on A marriage proposal spoken in office jargon
> boy

And nouns as interjections.

el_pollo_diablo··on The Byte Order Fiasco (2021)
Look, it's not that difficult:

  static inline uint32_t load_le32(void const *p)
  {
    unsigned char const *p_ = p;
    _Static_assert(sizeof(uint32_t) == 4, "uint32_t is not 4 bytes long");
    return
      (uint32_t)p_[0] <<  0 |
      (uint32_t)p_[1] <<  8 |
      (uint32_t)p_[2] << 16 |
      (uint32_t)p_[3] << 24;
  }
  
  static inline void store_le32(void *p, uint32_t v)
  {
    unsigned char *p_ = p;
    _Static_assert(sizeof(uint32_t) == 4, "uint32_t is not 4 bytes long");
    p_[0] = (unsigned char)(v >>  0);
    p_[1] = (unsigned char)(v >>  8);
    p_[2] = (unsigned char)(v >> 16);
    p_[3] = (unsigned char)(v >> 24);
  }
All that nonsense about masking with an int must stop. You want a result in uint32_t? Convert to that type before shifting. Done.

Now, the C standard could still get in the way and assign a lower conversion rank to uint32_t than to int, so uint32_t operands would get promoted to int (or unsigned int) before shifting, but those left shifts would still be defined as the result would be representable in the promoted type (as promotion only makes sense if it preserves values, which implies that all values of the type before promotion are representable in the type after promotion).

el_pollo_diablo··on 'Equals' has more than one meaning in math
Another way to see it is to prepend every mathematical text involving ℤ with "for every ℤ such that [essential properties omitted]", so that you can apply it to several definitions of ℤ, rather than awkwardly redefining it after the fact. This is the mathematical equivalent of "programming to the interface", and is actually how mathematics are often formalized in modern proof assistants: as huge functors that abstract these details away.
el_pollo_diablo··on Rust is not about memory safety
What does source code/proof maintenance have to do with what remains at runtime? Sure, you can always extract the computational part of a program by erasing the logical parts, but that does not imply that code intermixed with logical parts does not create maintenance issues.

Dependency management is one of those issues. Proofs require an acyclic dependency graph, in order to prevent circular arguments. By intermixing code and proofs, you force everything to fit in a single global dependency order. The point is not that it is impossible (it is possible), but that it is a maintenance nightmare. Sometimes you have to break an otherwise perfectly coherent module into smaller modules, just because you need to insert some other modules between them in the dependency order, that are only relevant to some minor proof. You have to constantly refactor your code as you reason on more aspects of your program. Have you already tested and certified your code and existing proofs? Too bad, your latest proof will require lots of handwaving and recertification to convince everyone that the big refactoring does not threaten the existing properties.

Runnable code stands on its own, and should not be polluted with logical parts for every aspect of the program one may want to reason about.

You can establish any provable property of a program using only basic logical tools: a single precondition and a single postcondition per function, a single invariant per loop, maybe dependent types, a few ghost values here and there, etc, and stuff all your reasoning in them in huge messy conjunctions mixing all the concerns together. That would be the equivalent of using nothing but a Turing machine to write a program. It is possible, it is theoretically appealing, but it does not scale.

Software engineering is a thing for a reason. So is proof engineering.

el_pollo_diablo··on Rust is not about memory safety
Disclaimer: my shop develops non-trivial low-level software with machine-checked correctness proofs.

Rice's theorem implies that automatic static analysis (like Rust's borrow checker) will only get you that far. To go further, you must equip the program with a proof, which can be an order of magnitude more complex than the program.

Don't get me wrong, Rust is excellent for developing security-critical applications. Its borrow checker solves many memory safety and concurrency issues, and its type system more generally forces error paths to be explicit. The next step would be to use deductive methods to check that the error paths cannot be taken.

> make invalid states unrepresentable

That is a nice ideal, but not very practical. You need dependent types for that (for example, a sigma-type that bundles a value in a carrier type with a proof that it satisfies an invariant). They have their uses (e.g. at the interface of a library), but they are a pain to work with. You must build the proof terms together with the runtime values, thus entangling program and proofs into an unmaintainable mess. Oh, and forget about modular proof development: the dependent type encodes every constraint on the value, therefore most types must change across the program when you decide to prove an additional property of the program. You can't just keep the existing proof around and prove something else on top of it.

By all means, please keep some invalid states representable, and cleanly separate the program from its various proofs.

el_pollo_diablo··on Henry Darger
I first learnt about Henry Darger in Olivia Laing's The Lonely City. It is a first-hand account of the psychological effects of loneliness and isolation. The author draws parallels between her own experience and that of other artists like Darger, and describes the way in which this experience can drive their creative process.
el_pollo_diablo··on A lock-free ring-buffer with contiguous reservations (2019)
There is this snippet of code in the article:

  if buffer.len.saturating_sub(buffer.write.load()) >= write_len {
    // not shown: check `read` to make sure there's enough free room
    buffer.watermark.store(buffer.write.load() + write_len);
    buffer.write.store(buffer.write.load() + write_len);
  }
I would have to look at the implementation to know for sure, but that part looks incorrect to me. Suppose that the writer has placed a watermark strictly before the end of the buffer, wrapped around, and is about to write a new message; meanwhile, the reader has not reached the watermark yet (and therefore, has not wrapped around), but it has made enough progress to leave room for the writer's new message. In that case, we have write <= write + write_len < read <= watermark < len. As written, it would seem that the snippet above would incorrectly update watermark, whose value is still needed by the reader.

It seems to me that watermark need not be atomic anyway: it is owned by the writer when read <= write, and by the reader when write < read. Whoever wraps around implicitly passes the ownership to the other thread. More precisely:

* In the initial state, and until the writer reaches the end of the buffer, read <= write, and the writer owns watermark, whose value is irrelevant. In particular, the reader makes sure not to overtake write, and knows that it must not access watermark.

* When the writer needs to wrap around, it first sets the watermark (possibly at len, if the hole is empty), then updates write. With its usual release memory ordering constraint, the atomic store to write transfers to the reader the ownership of the written messages, but also of watermark.

* Eventually, the reader notices that write has wrapped around, and then uses watermark to know where to stop reading. Meanwhile, the writer may fill the beginning of the buffer, carefully not overtaking read - 1, and never touching watermark.

* When the reader finally wraps around, the atomic write to read transfers to the writer the ownership of the consumed message slots, but also of watermark, and we are back in the first phase.

IOW, watermark has the same owner as the last element of the array.

What do you think? What have I missed?

el_pollo_diablo··on Atomics and Concurrency
There are many problems with this concurrent queue. Here are a few I found in a cursory reading.

In order to enqueue an element, you have to change two atomic pointers: tail->next and tail. That cannot be done atomically.

enqueue() assumes that the queue is not empty.

enqueue() happily overwrites current_tail->next even if it is not null (which may happen if some other producer has enqueued something since we read current_tail).

Then there is the old-time favourite ABA problem.

By the way, when used in a loop, compare_exchange_weak is preferred to compare_exchange_strong, and there is no need to reload the atomic every time: compare_exchange_* do that for you by updating the argument containing the expected value.

el_pollo_diablo··on Modern C for Fedora (and the World)
Not exactly. As of C17, the function definition you wrote implies that the function has no arguments, just like in C++. However, a declaration that is not part of a definition, like

  void fun();
(which you typically find in a header file) indeed does not say anything about the function's arguments. You have to write

  void fun(void);
to specify that the function takes no arguments. For consistency, you can (and probably should) also use that style in the function's definition, but you don't have to.

Anyway, C23 will align C's behavior with C++: void fun() will mean the same thing as void fun(void), whether as part of a function definition or not.

el_pollo_diablo··on So you want custom allocator support in your C library
Yes, that's item 2 of the checklist in the original article.
el_pollo_diablo··on So you want custom allocator support in your C library
> max_align_t is only the max for scalar types, typically 8 or 16 bytes. But often math-intensive code wants 16 or 32 byte alignment for float arrays, to enable SIMD operations.

Indeed, but _Alignof(max_align_t) is a good compromise for a default alignment requirement in an allocator interface, which is what eqvinox calls for. Standard C does exactly that: malloc(), realloc(), and calloc() promise that they satisfy _Alignof(max_align_t), but nothing stricter. To reach for extended alignment requirements, your only standard tool is aligned_alloc().

el_pollo_diablo··on So you want custom allocator support in your C library
> The context parameter already addresses that need.

How so? The context parameter identifies the allocator instance. What if the library needs to allocate objects with different alignment requirements with the same allocator instance?

Alignment requirement is just like allocation size (*). It varies from call to call, and generic allocators need to deal with heterogeneous alignments and sizes.

(*) Case in point: Rust's Allocator interface (https://doc.rust-lang.org/std/alloc/trait.Allocator.html) bundles them up in a single Layout object.

el_pollo_diablo··on So you want custom allocator support in your C library
> I don't have data on this but I feel that posix_memalign might be more widely supported than aligned_alloc.

Possibly. IIRC Microsoft's CRT does not support aligned_alloc() because their implementation of free() cannot deal with extended alignment requirements, so they have separate functions for aligned (de)allocation. To be fair, they probably do not support posix_memalign() either.

> it becomes a serious pain to go through all allocations and figure out a reasonable alignment value

Sure, you can pass _Alignof(max_align_t) in almost all cases, or have generic (= not reimplemented by each allocator) convenience wrapper functions that do that for you. If you want to pass the least restrictive alignment in all cases, you can enlist the help of a macro, but this is a bit more awkward. For instance:

  #define ALLOC(ptr, size) ((ptr) = alloc(_Alignof(typeof(*(ptr))), (size)))
  
  foo_t *p;
  ALLOC(p, 42 * sizeof *p);
(Note that this uses the typeof() operator, which should become standard with C23.)
el_pollo_diablo··on So you want custom allocator support in your C library
I don't think I have seen it in publicly available allocators either, but I once implemented it in a custom one. I suppose that this design is not very popular because it is quite fragile: you end up running arbitrary code (the move constructor) in the middle of an allocation routine, when some of the heap's invariants have not yet been restored. Consequently, you typically require that the move constructor not recursively call the allocator, which is a reasonable limitation.

Alternatively, the allocator could treat reallocation as a multi-step process ( a) reserve new space, b) move data, c) free old space), with enough state tracking to allow a) and c) to be different calls to the allocator, so that b) could be performed by the caller.

There is no perfect solution to this problem. I suppose that's why C++ does not have a standard reallocation counterpart to new/delete/new[]/delete[].

el_pollo_diablo··on So you want custom allocator support in your C library
C11 has aligned_alloc, which is more standard than posix_memalign, but there is no standard "aligned_realloc".

There is no default alignment if all the functions of the allocator take it as a parameter, but it is reasonable for an allocator implementation to be optimized for a particular alignment requirement such as _Alignof(max_align_t).

el_pollo_diablo··on So you want custom allocator support in your C library
If the library reallocates non-trivial objects, it may need a more sophisticated reallocation function, that does not simply bitwise copy a block to its new location. Some additional work may be needed (e.g. pointer fixup). The reallocation function could take a "move constructor" callback as parameter.
el_pollo_diablo··on So you want custom allocator support in your C library
Unless all objects allocated by the library have one of the fundamental alignment requirements, I'd add a fourth item to the checklist:

  4. All functions take the alignment requirement as a parameter. The alignment requirement must be a power of 2. The reallocation and deallocation functions must be passed the same alignment requirement value as was passed to the allocation function when the block was first allocated.
A common motivation for rolling out your custom allocator is dealing with extended alignment requirements. This should be reflected in the allocator's API.
el_pollo_diablo··on The Final Speech from The Great Dictator (1940)
My personal favorite is by Hugo Kant:

https://www.youtube.com/watch?v=wsWrU9h9WGI

el_pollo_diablo··on Unaligned accesses in C/C++: what, why and solutions to do it properly
Furthermore, one advantage of this solution over using memcpy is that the compiler can still understand what it does (and aggressively optimize it) in a freestanding environment.
el_pollo_diablo··on Unaligned accesses in C/C++: what, why and solutions to do it properly
Here is another solution for loading a potentially unaligned 64-bit integer in the CPU's byte order, that does not violate strict aliasing:

  uint64_t load64(uint8_t const *b) {
      union {
          uint64_t u64;
          uint8_t u8[8];
      } u = {.u8 = {
          b[0], b[1], b[2], b[3], b[4], b[5], b[6], b[7]
      }};
      return u.u64;
  }
Type punning through a union is explicitly supported by the C standard, insofar as we do not evaluate uninitialized memory or trap representations. We are fine here, as uint64_t has no trap representations, and must have exactly the size of 8 uint8_ts, as those types have no padding bits.

GCC appears to compile this function to a plain unaligned load at optimization level 2, when supported, e.g. on arm64 (see https://godbolt.org/z/frEox67sG).

← PreviousPage 2 of 2