5 ms·

People have probably reinvented generics thousands of times in C, mostly using function pointers or macro hacks. Edit: And the intrusive data structures common

People have probably reinvented generics thousands of times in C, mostly using function pointers or macro hacks. Edit: And the intrusive data structures commonly used in C are way more complicated than the equivalent generic code (in my opinion). https://lwn.net/Articles/184495/ https://lwn.net/Articles/184495/

codr7 7y ago
You can write Fortran in any language, these people are missing the point. The simplicity is a feature, it also allows you to say exactly what you mean without sweet talking the compiler.
- giornogiovanna 7y ago
  What should I do in Go or C if I want a red-black tree? As far as I know, my options are: - Download one that uses interface{} / void pointers - okay, but not very efficient or type-safe. - Download one that's intrusive - okay, but pretty convoluted. - Write my own - a pain. - Code generation - generics but worse. (This isn't sarcastic.)
  - foldr 7y ago
    Well, your list does include three practical options. Using interface{} is the go-to option and usually works fine. The overhead of interface{} isn't as high as people sometimes think. You have the overhead of boxing the value, but the actual type checking is just a single comparison and jump.
    - sacado2 7y ago
      > You have the overhead of boxing the value, but the actual type checking is just a single comparison and jump. This is way too much in a tight loop. I want my structure to fit in the cache and I want to have as little tests as possible.
      - foldr 7y ago
        Most of the time it won't actually be "too much". The comparison itself has very little overhead due to branch prediction. But yes, if you're writing performance critical code (which you generally won't be), then you'll need to use code generation to avoid boxing. This kind of discussion is pointless without some kind of real world reference point. The vast majority of Go projects will never run into a situation where the overhead of using interface{} is a performance bottleneck. If you're working on a project where you consistently have to think about the cache performance of your code, then C++ or Rust would probably be better choices. Go isn't meant to be all things to all people.
        sacado2 7y ago
        If you want a real-world example: I struggle with my SAT solver, gophersat[1]. I have different kinds of constraints, mainly propositional clauses (a or b or c) and pseudo-boolean constraints (2a + b + c >= 2). Long story short, a propositional clause is a special kind of pseudo-boolean constraint, so I can process my clauses as if they were regular pseudo-boolean constraints, but this is slower than using dedicated code. Lots of problems only deal with propositional clauses, so they take longer to solve than they should, because I cannot say "this is a problem with only propositional clauses", vs "this is a problem with all kinds of clauses". I could use interfaces, and tried, but this is way slower, to the point it doesn't make sense to use them. And I can't use C++ or rust for this problem: there are already tons of very good c++ SAT solvers, but my goal was to provide a SAT solver I can use in my go programs without resorting to cgo black magic. [1]https://github.com/crillab/gophersat https://github.com/crillab/gophersat
        foldr 7y ago
        Neat project. Yes, fair enough, I think that is a good example of the kind of code that Go is not particularly suited to (if performance is critical).
      - jerf 7y ago
        "This is way too much in a tight loop. I want my structure to fit in the cache and I want to have as little tests as possible." If that is a hard requirement, then the answer is just that Go isn't a suitable language. AIUI the current generics proposal in Go, it won't fix that problem for you either. Where I disagree with the programming community at large is how often that's actually a hard requirement. A lot of programmers grossly overestimate their performance requirements on the microscale [1], and so concerns about "premature optimization" remain alive and well decades later. However, there are undeniably still a non-trivial number of cases where that really is a hard requirement, in which case the answer is, don't use Go. (Preferably, figure that out before you start. As a fairly heavy Go user, I actually kinda cringe when reading one of the several "We sped up Go by 10x on our particular big thing and got to barely-acceptable performance" articles, rather than consider it something to be celebrated. I mean, cool that you sped it up that much and all, but honestly the correct answer was to notice in the design phase that you were doing something you probably shouldn't have done in Go, modulo concerns about easy prototyping and such.) [1]: I qualify with "microscale" because I also think a lot of programmers underestimate the performance requirements on the macro scale. But that's actually a very different issue. There's a lot of very sluggish and slow code out there in the wild that is architecturally wrong; at every individual step the code is reasonably optimized and fast, the problem is having the wrong steps.
    - bsaul 7y ago
      the term « boxing » was very often used before C# had proper generics, and the same goes for java when Object was used everywhere ( priori to generics). Then generics came in an everybody talked about type safety and performance gains. Then 10 years later horrendous over-complexified designs started to cripple code bases all over the world. I honestly wonder if go isn’t cursed to follow the same road.
      - foldr 7y ago
        "Boxing" just means storing a (possibly tagged) pointer to a value rather than the value itself. It has nothing specifically to do with generics. But yeah, I share your concern. It would be nice to have a better way to write container types in Go, but generics always seem to end up getting abused.
      - tluyben2 7y ago
        My Java days are long gone, but modern C# code is not overly complex and, if you use fp principles where you can, even really quite simple to read. Ofcourse you have OOP design pattern addicts who write hard to follow overarchitected stuff, but your language cannot prevent that; people write convoluted stuff in any language. Blaming just generics for that does not work imho; in Java people were writing really insanely over complex code close after the first release; I had an ex C++ guy before 2000 writing Java code that used every design pattern in The Book, everywhere he could and it ended up with 1000s of files and those strange long names that became the standard for Java a few years later.
    - eropple 7y ago
      > The overhead of interface{} isn't as high as people sometimes think. The cognitive overhead certainly is. Computers exist to help us do things faster and with fewer mistakes. This is a prime example of using a computer to help us make more mistakes, worse.
      - foldr 7y ago
        Yes, using interface{} introduces a small chance of runtime type errors. I have not heard of any Go projects finding this to be much of a problem in practice. You can also use the type-safe wrapper pattern to avoid this if it's likely to be a problem. There is no doubt that not having generics makes some code worse than it would be with generics. But I think the problem is often overstated.
  - marcosdumay 7y ago
    In C you'll content yourself with a library for operations on long, long long, or void*. But if you are working on a project where the details of the tree do not matter (so you can use a library), you will probably use C++, not C. I still have a hard time understanding what niche Go fills, it's too high level to compete with C or Rust, but here we are comparing its expressiveness with C.
rumcajz 7y ago
The question of intrusive containers is kind of orthogonal. You can implement intrusive containers using generics. Aslo, kernel code would use intrusive containers even if there were easy-to-user non-intrusives available directly in C. The reason, of course, being that with intrusive containers you can avoid huge amount of memory allocations.
- deleted 7y ago
  [deleted]
wahern 7y ago
The Linux kernel is the last place anybody should go to find simple, clean interfaces. That's just not how Linux rolls--almost everything else has a higher priority. The classic intrusive data structure in C is the link-list as implemented in BSD (though I'm sure it predated BSD): https://man.openbsd.org/queue#LIST_EXAMPLE https://man.openbsd.org/queue#LIST_EXAMPLE A red-black tree implemented in the same simple style by an OpenBSD developer a couple of decades later was adopted almost overnight by all BSDs: https://man.openbsd.org/tree#EXAMPLES https://man.openbsd.org/tree#EXAMPLES Unlike the Linux version, the BSD version is as type-safe as a C++ template, permits a node to exist in as many collections as you want (one member field per collection), and like a template the BSD version can inline the comparison function. You even have the option of making all the routines extern or static, which you can't even do with C++ templates. What the Linux version has going for it is that it doesn't need to rely on the preprocessor so the implementation looks a little neater and more like a C++ template--no columns of backslashes as required with preprocessor-based generation. But that's a horrible tradeoff. queue.h and tree.h have basically been frozen for decades.[1] After initial curiosity wanes (day #2 of many thousands), nobody reads the headers because the interface is simple and never changes. [1] Various systems have tweaked things here and there (e.g. to add parameterized trace points), but the original APIs never changed and code has always remained portable at the source level. The only big change over all that time was most systems (BSDs, macOS) eventually dropped CIRCLEQ after someone (I think a FreeBSD developer) posted benchmarks showing it sucked relative to TAILQ. I actually preferred CIRCLEQ; the entire header is small enough that for awhile I just copied it around everywhere.

codr7 7y ago

You can write Fortran in any language, these people are missing the point. The simplicity is a feature, it also allows you to say exactly what you mean without sweet talking the compiler.

giornogiovanna 7y ago
What should I do in Go or C if I want a red-black tree? As far as I know, my options are: - Download one that uses interface{} / void pointers - okay, but not very efficient or type-safe. - Download one that's intrusive - okay, but pretty convoluted. - Write my own - a pain. - Code generation - generics but worse. (This isn't sarcastic.)
- foldr 7y ago
  Well, your list does include three practical options. Using interface{} is the go-to option and usually works fine. The overhead of interface{} isn't as high as people sometimes think. You have the overhead of boxing the value, but the actual type checking is just a single comparison and jump.
  - sacado2 7y ago
    > You have the overhead of boxing the value, but the actual type checking is just a single comparison and jump. This is way too much in a tight loop. I want my structure to fit in the cache and I want to have as little tests as possible.
    - foldr 7y ago
      Most of the time it won't actually be "too much". The comparison itself has very little overhead due to branch prediction. But yes, if you're writing performance critical code (which you generally won't be), then you'll need to use code generation to avoid boxing. This kind of discussion is pointless without some kind of real world reference point. The vast majority of Go projects will never run into a situation where the overhead of using interface{} is a performance bottleneck. If you're working on a project where you consistently have to think about the cache performance of your code, then C++ or Rust would probably be better choices. Go isn't meant to be all things to all people.
      - sacado2 7y ago
        If you want a real-world example: I struggle with my SAT solver, gophersat[1]. I have different kinds of constraints, mainly propositional clauses (a or b or c) and pseudo-boolean constraints (2a + b + c >= 2). Long story short, a propositional clause is a special kind of pseudo-boolean constraint, so I can process my clauses as if they were regular pseudo-boolean constraints, but this is slower than using dedicated code. Lots of problems only deal with propositional clauses, so they take longer to solve than they should, because I cannot say "this is a problem with only propositional clauses", vs "this is a problem with all kinds of clauses". I could use interfaces, and tried, but this is way slower, to the point it doesn't make sense to use them. And I can't use C++ or rust for this problem: there are already tons of very good c++ SAT solvers, but my goal was to provide a SAT solver I can use in my go programs without resorting to cgo black magic. [1]https://github.com/crillab/gophersat https://github.com/crillab/gophersat
        foldr 7y ago
        Neat project. Yes, fair enough, I think that is a good example of the kind of code that Go is not particularly suited to (if performance is critical).
    - jerf 7y ago
      "This is way too much in a tight loop. I want my structure to fit in the cache and I want to have as little tests as possible." If that is a hard requirement, then the answer is just that Go isn't a suitable language. AIUI the current generics proposal in Go, it won't fix that problem for you either. Where I disagree with the programming community at large is how often that's actually a hard requirement. A lot of programmers grossly overestimate their performance requirements on the microscale [1], and so concerns about "premature optimization" remain alive and well decades later. However, there are undeniably still a non-trivial number of cases where that really is a hard requirement, in which case the answer is, don't use Go. (Preferably, figure that out before you start. As a fairly heavy Go user, I actually kinda cringe when reading one of the several "We sped up Go by 10x on our particular big thing and got to barely-acceptable performance" articles, rather than consider it something to be celebrated. I mean, cool that you sped it up that much and all, but honestly the correct answer was to notice in the design phase that you were doing something you probably shouldn't have done in Go, modulo concerns about easy prototyping and such.) [1]: I qualify with "microscale" because I also think a lot of programmers underestimate the performance requirements on the macro scale. But that's actually a very different issue. There's a lot of very sluggish and slow code out there in the wild that is architecturally wrong; at every individual step the code is reasonably optimized and fast, the problem is having the wrong steps.
  - bsaul 7y ago
    the term « boxing » was very often used before C# had proper generics, and the same goes for java when Object was used everywhere ( priori to generics). Then generics came in an everybody talked about type safety and performance gains. Then 10 years later horrendous over-complexified designs started to cripple code bases all over the world. I honestly wonder if go isn’t cursed to follow the same road.
    - foldr 7y ago
      "Boxing" just means storing a (possibly tagged) pointer to a value rather than the value itself. It has nothing specifically to do with generics. But yeah, I share your concern. It would be nice to have a better way to write container types in Go, but generics always seem to end up getting abused.
    - tluyben2 7y ago
      My Java days are long gone, but modern C# code is not overly complex and, if you use fp principles where you can, even really quite simple to read. Ofcourse you have OOP design pattern addicts who write hard to follow overarchitected stuff, but your language cannot prevent that; people write convoluted stuff in any language. Blaming just generics for that does not work imho; in Java people were writing really insanely over complex code close after the first release; I had an ex C++ guy before 2000 writing Java code that used every design pattern in The Book, everywhere he could and it ended up with 1000s of files and those strange long names that became the standard for Java a few years later.
  - eropple 7y ago
    > The overhead of interface{} isn't as high as people sometimes think. The cognitive overhead certainly is. Computers exist to help us do things faster and with fewer mistakes. This is a prime example of using a computer to help us make more mistakes, worse.
    - foldr 7y ago
      Yes, using interface{} introduces a small chance of runtime type errors. I have not heard of any Go projects finding this to be much of a problem in practice. You can also use the type-safe wrapper pattern to avoid this if it's likely to be a problem. There is no doubt that not having generics makes some code worse than it would be with generics. But I think the problem is often overstated.
- marcosdumay 7y ago
  In C you'll content yourself with a library for operations on long, long long, or void*. But if you are working on a project where the details of the tree do not matter (so you can use a library), you will probably use C++, not C. I still have a hard time understanding what niche Go fills, it's too high level to compete with C or Rust, but here we are comparing its expressiveness with C.

rumcajz 7y ago

The question of intrusive containers is kind of orthogonal. You can implement intrusive containers using generics. Aslo, kernel code would use intrusive containers even if there were easy-to-user non-intrusives available directly in C. The reason, of course, being that with intrusive containers you can avoid huge amount of memory allocations.

deleted 7y ago
[deleted]

wahern 7y ago

The Linux kernel is the last place anybody should go to find simple, clean interfaces. That's just not how Linux rolls--almost everything else has a higher priority. The classic intrusive data structure in C is the link-list as implemented in BSD (though I'm sure it predated BSD): https://man.openbsd.org/queue#LIST_EXAMPLE https://man.openbsd.org/queue#LIST_EXAMPLE A red-black tree implemented in the same simple style by an OpenBSD developer a couple of decades later was adopted almost overnight by all BSDs: https://man.openbsd.org/tree#EXAMPLES https://man.openbsd.org/tree#EXAMPLES Unlike the Linux version, the BSD version is as type-safe as a C++ template, permits a node to exist in as many collections as you want (one member field per collection), and like a template the BSD version can inline the comparison function. You even have the option of making all the routines extern or static, which you can't even do with C++ templates. What the Linux version has going for it is that it doesn't need to rely on the preprocessor so the implementation looks a little neater and more like a C++ template--no columns of backslashes as required with preprocessor-based generation. But that's a horrible tradeoff. queue.h and tree.h have basically been frozen for decades.[1] After initial curiosity wanes (day #2 of many thousands), nobody reads the headers because the interface is simple and never changes. [1] Various systems have tweaked things here and there (e.g. to add parameterized trace points), but the original APIs never changed and code has always remained portable at the source level. The only big change over all that time was most systems (BSDs, macOS) eventually dropped CIRCLEQ after someone (I think a FreeBSD developer) posted benchmarks showing it sucked relative to TAILQ. I actually preferred CIRCLEQ; the entire header is small enough that for awhile I just copied it around everywhere.