21 ms·

Modern programming languages require generics

• formerly_proven 4y ago
  > Java is the only one on this list that has a different approach. Instead of using generics at compile time, it is actually doing a dispatch of the code to optimized routines based on runtime types. That does mean that they had to write the same sort code multiple times, of course. > Using Java: public static void sort(int [] a); public static void sort(long[] a); public static void sort(Object[] a); Perhaps they meant it another way, but this makes it sound like there is runtime dispatch between these different signatures - there isn't. int, long etc. are unboxed types in Java, which are not Objects, and cannot be used for Object-based generic type-erasure. So the decision which of these sorts is going to be used is made by the compiler. All Objects are sorted using the third signature.
  • zwieback 4y ago
    Yes, seems like Java generics are an argument against the "generics allow optimization" argument. Maybe I misunderstood what he was trying to say.
    • lifthrasiir 4y ago
      Generics allow optimization, but that optimization has to be implemented in the first place. Java generics is an afterthought so you can expect such a suboptimal design.
      • malfist 4y ago
        Features added after launch doesn't make something an afterthought. Java generics are a key part of the language.
        • switchbak 4y ago
          Generics were only added in Java 1.5, they were absolutely not part of the original design, and type erasure is very much a considerable restriction in some cases. I would wager that a greenfield design would look quite different. Whether you call that an afterthought? I'm sure the designers had this in mind, but at the same time they painted themselves into a corner somewhat with earlier decisions and a huge dedication to backward compatibility. Their work on threads on the other hand shows some real forethought and they were able to avoid most of the pitfalls that a few other language impl's fell into.
        • wvenable 4y ago
          Generics in C# were also added after launch but have a significantly better implementation. While they are a key part of the language they aren't a key part of the platform.
      • cogman10 4y ago
        Java optimizes at the method level and the majority of methods when writing an app will have constant types used against them. Your method signature may look like void foo(Iterable<Bar> b) which would make you think of vtables and casting performance losses. However, Java's JIT is fairly cleaver. It can tell that you always call `foo` with an `ArrayList` and it can tell that `ArrayList`'s iterator always emits a `Bar` Object. From there it can elate a lot of the type tables and virtual dispatch to just be direct dispatch. It does that at the cost of a couple of added runtime checks to make sure those assumption's aren't violated. The impact of generics on performance has, for me, generally been pretty low. I've seen a much higher impact due to java's memory model (which is getting fixed with Valhalla). This, btw, is how JavaScript's and indeed most high speed JITs function.
        • lifthrasiir 4y ago
          Yeah, JIT does subsume naive AOT + generics for many cases, but it is a bit unfair comparison because there is no reason for other languages to implement such optimizations (PGO is one of them). And such an inference is not free and causes usual JIT pain points.
      • kaba0 4y ago
        I don’t think it is fair to call it an afterthought. I would even say that it was extremely well thought out, managing to move a whole ecosystem with millions of lines of code from unsafe raw usage to type-safe generics without much hiccup, at a time when this feature wasn’t all that well known by the average developer.
        • titzer 4y ago
          Erasure was a bad design choice. C# did the exact same upgrade (add generics to the language), but they chose to reify them and add them to the binary format, with a better overall result (IMHO). C# does not have platform reach that Java has, but there are a lot of factors at play there that go beyond language design choices.
          • kaba0 4y ago
            As I learned from another commenter here, C# 1.0 didn’t actually have generics at a language level, but was already designed that way on a vm level. So C# 2.0 could take advantage of that, making it much more of a planned feature from the start. Also, I don’t see erased generics all that big of a deal — if there was no reflection (which is not that common feature in languages) one could not even differentiate between the two models. Haskell also does complete type erasure for example. As for another view point, it is often brought up on HN that what made the JVM language ecosystem so thriving is exactly the type erasure model. C# effectively forces their idea of generics onto the whole platform, while JVM languages are free to choose their own model. I don’t know how true is that, but empirically it does seem to sound true (F# does share its generics model with C#, and the CLR has a history of getting some attempts at being a target which is later dropped. Though I assume it is more often due to it simply being a smaller target)
            • titzer 4y ago
              > if there was no reflection (which is not that common feature in languages) one could not even differentiate between the two models. Haskell also does complete type erasure for example. You can, even without reflection, because the Java generic type system doesn't have the parametricity property; you can detect runtime types with cast/instanceof. Haskell doesn't have non-parametric operations, so erasure is not observable.
    • marginalia_nu 4y ago
      The path Java chooses for optimization is through JIT, but that's entirely orthogonal to generics. Java generics are a syntactic construction, there really is no JVM support for them what so ever.
      • cogman10 4y ago
        It's complicated. There actually IS JVM support for generics in surprising locations. Just not at method dispatch... sort of. For example void <T extends Foo> bar(T f); will, under the covers, create a function that looks like void bar(Foo f); If you create a class class Foo implements Supplier<Bar> { Bar get() { return new Bar(); } } The method signature for `Foo` does in fact return a `Bar` type and not some `Object` type even though `Supplier<Bar>` would imply that is erased. The same applies to if that generic was used within the method parameters. That generic type information is, in fact, stored off at the class level and can be extracted through Java's reflection API. This is how magic like json.parse("[1,2,3]", new TypeReference<List<Integer>>{}); is getting it's stuff done. It's creating a new anonymous class of "TypeReference<List<Integer>>" which the json library can then use to introspect and pull the generic information out and know that it should create a `List` of `Integer` rather than of `Long` or `Double` or a `Set`. This makes generics more than just a syntactic construction in Java.
        • marginalia_nu 4y ago
          class Foo implements Supplier<Bar> { Bar get() { return new Bar(); } } Bar isn't a generic in Foo though (if we remove the implements-clause, that is very clear). It's only a generic in Supplier, so I don't see where the implied erasure quite comes from.
          • cogman10 4y ago
            I didn't add it, but the `get` method comes is an override from the `Supplier`. For example, if we did something like class Foo extends HashMap<Foo, Bar> { @Override Bar put(Foo f, Bar b) { super.put(f, b); } } The `Map` signature for `put` is `Object put(Object, Object)` due to erasures. However, because you are extending and specifying the generics, the overriden method ends up reifying the type. All this is to say that generics end up being a little more than just syntactic sugar.
    • mumblemumble 4y ago
      I think the author got it slightly wrong here because he's conflating the programming language feature and its semantics with the run-time implications of the technique(s) you use to implement that feature. For what it's worth, this seems to be a common misunderstanding where generics are concerned.
    • kaba0 4y ago
      That is also not true — Java’s generics don’t add any overhead. If you would have written an ArrayList implementation before generics you would have had the exact same compiled method signature like put(Object o) and Object get() - the only difference is that it would not have been type safe, that is you could have inserted a String into it while you might have expected to get an Integer on the other side. So generics are completely a language semantic concept in case of Java, with no performance detriment/benefit. Of course more information can be used up for better optimizations as well, see Rust’s or C++’s generics/templates.
      • titzer 4y ago
        The javac source compiler erases source-level types and inserts casts into the bytecode (at usage sites, not within the generic class). So if you have ArrayList<T>, it will generate one version of ArrayList. But usage sites will have casts inserted where necessary. In particular, in a use of put() on the outside doesn't need a cast (because the single implementation of ArrayList uses Object underneath), but get() will have a cast from Object to String at the call site.
  • dcminter 4y ago
    Plus I don't know about you, but I don't sort (or really use) arrays in Java very much. I see a lot more of the Collections.sort() methods, particularly the comparator based one.
    • marginalia_nu 4y ago
      Sorting arrays of primitives ought to be nearly as frequent as the need for sorted arrays of primitives due to the downright comical overhead of List<Integer>, but sorting arrays of objects has be rare in Java code written this millennium.
      • dcminter 4y ago
        I mean I don't sort List<Integer> more than once in a blue moon either. I'm much more likely to either be sorting a list of model objects with a comparator, or manipulating a collection of objects that's already been sorted by some external source. In the unlikely event that I'm modeling something that can be represented as a list of integers AND it's a significant performance bottleneck then, sure, I'll consider the array methods. But I don't recall the need arising in the last year or two. Enterprise Java stuff just isn't often bottlenecked on that sort of thing. Network latency fills far more of my dreams ;)
        • marginalia_nu 4y ago
          Maybe we're seeing different sides of the language then. I'm doing a lot of integer-list sorting, building a search engine in java. I'm evenly split between Arrays.sort or GNU Trove's specialized primitive collections. The overhead of List<Integer> really can not be overstated, it can approach order 1000% memory consumption, speed is prima facie about half for dealing with collections, but in practice it can be much lower from the GC churn. Even for lists as small as a million entries this can be quite untenable.
          • Scarbutt 4y ago
            Maybe we're seeing different sides of the language then. You are not seeing different sides of the language but participating in different domains, application/business logic programming vs more system level stuff.
  • taeric 4y ago
    Yeah, this really needs to point out that the elements in Arrays.sort have to be Comparable. More, they have to be Comparable with each other. Should probably show the Collections.sort that takes a Comparator to really make the point that that is dispatched at runtime. But then you would probably need to cover just how aggressive the JIT is in the JVM and how the costs may not be what you would think they are.
    • GordonS 4y ago
      You're not wrong, but I feel like this doesn't need explicitly spelled out, as it would be obvious to any Java dev (or C#, or indeed probably any language with generics).
      • taeric 4y ago
        I think my problem is that there is no runtime dispatch between the methods that were listed. Such that that was a bit of a non-sequitur for the point at hand.
  • Koshkin 4y ago
    This has little (nothing?) to do with generics, though. This is an example of function (name) overloading.
    • tialaramex 4y ago
      The technical term for this feature in this context is "ad hoc polymorphism". It's polymorphic because it only allows you to specify different types, you can't just go around making six different foo() methods that all take a string - that doesn't work because the compiler can't tell which one you wanted, and it's ad hoc because you can just fill out whatever you want in each version. The negative consequence of being ad hoc is that there's not even a very strong implication beyond the name that these different functions all do the same thing, and sure enough they often don't. So now either your users must read your documentation very carefully, or sometimes they will have unhappy accidents. This is made worse in many modern languages with type inference where your users may be mistaken about which of the functions they're actually calling since they don't always know the type of anything anyway... Ad hoc polymorphism is over-used because it is relatively cheap to implement, and it's cheap to add more of these overrides later.
      • Koshkin 4y ago
        Well, having methods in different classes that happen to share the same name is also an example of that, and so it cannot be avoided (not in practice, anyway).
  • charcircuit 4y ago
    >All Objects are sorted using the third signature. Just to be pedantic int[] and long[] are both objects, but will be sorted using the first two signatures because the JVM uses different instructions for loading and storing elements from an array. Technically you could make a single function to return an array's length since it uses the same instruction.
    • anonymoushn 4y ago
      This surely meant "All arrays of Objects"
  • mrighele 4y ago
    Java generics works only on reference types (i.e. anything that derives from Object), and not on primitive types like int and long. For this reason, if you want a method that work on both primitives and reference types, you have to provide distinct implementations. This is true even if you provide a generic version like public static <A> void sort(A[] e); You will not be able to use the above method with an int[]. Whenever possible the compiler will try to be helpful, and automatically box/unbox primitives for you, so for example the following will work public <A> A max(A a1, A a2); /* ... */ void foo() { int x = max(1,2); } this comes at the cost of boxing ints inside Integer, though. So, if you ignore for a moment primitives types, whenever you have generics, everything boils down to a single method accepting Objects and returning Objects. What the JVM does is to do runtime profiling of what actually you are passing to the generic method, and generate optimized routines for the "best case". In theory this is the best of the two worlds, because (unlike, let's say, C++) you will have a single implementation of the method, avoiding code explosion, but if you use it in an hot spot you get the optimized code. In a way, it is quite wasteful, because you throw away a lot of information at compile time, just to get it back (and maybe not all of it) at runtime through profiling, but in practice it works quite well. A side effect of this is this makes the JVM a wonderful VM for running dynamic languages like Ruby and Python, because that information is _not_ there at compile time. In particular GraalVM/Truffle and exposes this functionality to dynamic language implementations, allowing very good performance (according to their website [1][2], Ruby and Python on Truffle are about 8x faster than the official implementation, and JS in line with V8) [1] https://www.graalvm.org/ruby/ https://www.graalvm.org/ruby/ [2] https://www.graalvm.org/python/ https://www.graalvm.org/python/
    • amenghra 4y ago
      The state of Java’s type erasure makes me quite sad when I need the type information via introspection. I’d say the best situation would be keep the type information at compile time but let the VM decide if multiple implementations are needed or not at runtime.
      • admax88qqq 4y ago
        What information do you need that's gone? Type erasure happens but the objects still carry their true dynamic type with them, isn't that sufficient?
• jimbokun 4y ago
  More often, I see the argument for generics in terms of developer productivity. This author is making the case in terms of improved performance, which I find interesting.
  • taeric 4y ago
    Is a popular refrain for statically known types. If you can trade some compute from run to compile time, it can obviously speed up runtime.
  • mrweasel 4y ago
    I’m still surprised that generics increase performance. I also don’t fully understand how.
    • jacksnipe 4y ago
      Monomorphization generally opens the door for faster execution on a modern processor. If you have a layer of indirection (i.e., no genetics so you need to dispatch at runtime) then you wind up with an additional jump instruction. While modern processors and branch prediction make jumps relatively cheap, they can’t avoid instruction cache misses if the dispatch is happening frequently. By removing the layer of indirection, the compiler can choose to inline the implementation instead of using a jmp; this keeps our icache clean, and can lead to faster execution. However, there’s a real cost to this! Inlining is, in broad strokes, often faster; but that’s not always true if you’re e.g. inlining a large number of instructions into a tight loop. As with all performance, profile to know the truth.
      • kaba0 4y ago
        What is more meaningful perhaps is not the lack of jump, but another optimization “pass” after the inline. Let’s say the compare function needs an object passed to it (e.g. in Java’s case). In this case the call site would create two new objects, pass them to the compare function and jump there. Instead in case of an inline and optimization case the call site might avoid object creation entirely if they would only be destructured in the compare part.
• rahimiali 4y ago
  The article is fun to read, but I’m not convinced C’s lack of generics prevents it from supporting fast generic sort. Imagine qsort() being a header library, and a compiler that can inline heavily. What would prevent C from inclining the compare() function, recover the element types and produce specialized sorts?
  • unwind 4y ago
    The compare function is passed by value (like all things in C) and the preprocessor is not smart enough to find the code.
    • brabel 4y ago
      Does the necessary pointer casting in the implementations also make it slower than it should be (the specialized versions generated by compilers that support generics wouldn't have any casting)?
      • eptcyka 4y ago
        Its not the pointer casting, its the indirect function call that probably can be cached but it will always be another memory location that the CPU will need to jump to.
        • jjnoakes 4y ago
          If the compare function is inlined into the qsort() body, there wouldn't need to be any function call. I think that was the point of the question above.
          • OnACoffeeBreak 4y ago
            The way to answer this question is to look at the assembly code generated by the compiler with various optimization levels and see whether the compiler ever inlines the compare function. https://godbolt.org/ https://godbolt.org/ might be useful for this exercise.
• unwind 4y ago
  Very interesting and technical good post! Found a bug though: the C qsort() comparison callback needs to be able to express a being less than b by returning a negative value. The post's returns 0 if equal or 1 if greater. My typical implementation for numerical types goes return a < b ? -1 : a > b;
  • rjh29 4y ago
    Complete aside, one fun thing about Perl is it has an operator for this: a <=> b The 'spaceship' operator. You can sort an object by its foo property, then bar property, with: sort { $a->foo <=> $b->foo || $a->bar <=> $b->bar } @array; Python is still better IMO: sorted(array, key=lambda x: (x.foo, x.bar))
    • ncmncm 4y ago
      Another aside, C++ also has the spaceship operator. If you define it, the compiler generates implicit declarations for ==, <, >, etc. You can provide your own ==, too, if that would be faster, and the compiler will use that to generate !=. There can still be reasons to define all the operations explicitly, but those are rarely encountered. Even further aside, in discussing language features and design, the expression "but those are rare" comes up frequently. For different languages, its meaning may be radically different. In C++, it means "for that case, you have to do something a little less convenient". For almost all languages, it means "we don't handle that case, you're on your own". That depth is what has kept C++ on top of the performance and major system implementation heap for decades, not just, as is often asserted, inertia. Achieving depth takes decades.
  • jstimpfle 4y ago
    Also possible: return (a > b) - (a < b);
• lifthrasiir 4y ago
  The title doesn't exactly reflect the contents. It should have been "modern programming language that aims for high performance require generics", which is in my opinion close to the truth. It is a different matter whether a modern programming language should aim for high performance or not.
  • adgjlsfhk1 4y ago
    well, the 2 main reasons to make a new language are higher performance and higher productivity. Generics are a clear win for productivity, but there's less widely available info on their affect on performance.
    • kaba0 4y ago
      C++ can be plenty faster than C, not in small part due to its templates.
  • eterevsky 4y ago
    Modern programming languages that don't aim for high performance can just resort to duck typing or a similar way to emulate generics at runtime.
    • lifthrasiir 4y ago
      Static vs. dynamic typing has nothing to do with performance. You can have a reasonably performant implementation with dynamic typing, or conversely a statically typed language with zero concern about performance.
      • jstimpfle 4y ago
        That's empirically not true. The dynamic language (implementation) that is closest to static typing performance is probably Javascript, and it achieves this using an absurd amount of work to infer static types and to jit the code. If instead you make the reasonable assumption that dynamic typing => pointer indirection, and look at how memory works in modern machines, it's also theoretically untrue for a huge number of programs.
• layer8 4y ago
  Not providing generics was already a mistake > 25 years ago. Coming from C++ with its templates, I was astonished when Java came out without generics in 1995. It was dumbfounding, because parametric polymorphism was so obviously an essential feature for static typing (otherwise one has to resort to runtime type-casts all the time, relinquishing compile-time type safety), and Java was positioned as an alternative to C++. It took ten years for generics to finally be added to Java. (And another four years later Go came out, again without generics…) I later read an article or interview that one of the original Java implementers actually pushed for generics, but it was too much work/complexity and they wanted to get the language out.
  • golergka 4y ago
    It might have been understandable in 1995, because by then C++ already was mind-boggingly complex for a lot of applications, and it might not have been entirely clear which of it's features were the worst in that regard. But I was only starting programming with QBasic in 1995, so this is just a thought, not a fact.
    • jeremyjh 4y ago
      I think there were already much better models to follow than C++, in ML for example.
    • Jtsummers 4y ago
      Ada generics are easy to understand and were at least publicly known for ~12 years in 1995 (going by the publication date of the first Ada standard, older if we go to drafts and discussions prior to that standard's release). Generics aren't hard to use, and they aren't novel. That there's any debate nearly 40 years after at least one major procedural language introduced them is mind-boggling to me.
      • johnisgood 4y ago
        People really ought to look into Ada more. The language has a pretty neat type system (ranges are neat!), and it even has proper language constructs to do concurrent programming in it (had it for quite a while!). FWIW, search for "generic" here: https://en.wikibooks.org/wiki/Ada_Style_Guide/Concurrency https://en.wikibooks.org/wiki/Ada_Style_Guide/Concurrency
• nemo1618 4y ago
  Essentially every language provides some form of generics. Even Go 1.0 had `append` (a polymorphic function) and `map[K]V` (a polymorphic type). What Go 1.0 didn't have was user-defined generics. I am still of the (unorthodox) opinion that adding more built-in generics would have been a better solution than opening the door to arbitrary user-defined generics. Providing a generic `sort`, `reverse`, and a few others would cover 90% of the cases mentioned in every "Go needs generics!!" article.
  • HL33tibCe7 4y ago
    Which other built-in generics should have been added?
  • dhagz 4y ago
    Honestly, I enjoy the current answer to this (which was around long before Go's generics) - there is the `sort` package, which provides a lot of baseline sorting functions for built-in types, and then a function that takes a slice of `interface{}/any` and a function to sort the elements of that slice.
  • kaba0 4y ago
    The problem is that there is no mechanism that can deal with the remaining 10%. You either copy-paste code, add overhead or use some macros. For languages that are not well-suited for the last option we can see how “well” it turned out in case of C, where everyone has their own data structure lib, or use goddamn linked lists in a supposedly performant low-level language.
    • jstimpfle 4y ago
      Generic solutions are certainly not "the remaining 10%".
    • nemo1618 4y ago
      I think the idea that a languages ought to cover 100% of possible usecases has done far more harm than good. It's a ridiculously high bar. We should aim for more "Pareto-optimized" languages -- languages that address 80% of the problem space with 20% the complexity.
• Zababa 4y ago
  Discussed yesterday, 24 comments https://news.ycombinator.com/item?id=31475765 https://news.ycombinator.com/item?id=31475765.
• duped 4y ago
  I think it would be better said that contemporary languages should consider research in PL design and type theory over the last few decades. There is a trend it seems to discard it as "academic" (never mind the academics need to be brought in eventually, as in Go's generics). It feels like there's a lot of wheel reinvention going on, all the time. Especially with systems languages. Rust is the one that seems to "get it" (bite the bullet on syntax and learning curve, but give you reliable software that is pretty fast). I'm still waiting on Jai to be made public to see what is going on there.
• x-shadowban 4y ago
  Generics or otherwise, I just want type info to flow into and out of things like 'map' or 'SpecialContainer<T>', and for my editor to surface that information.
• badsectoracula 4y ago
  C doesn't require you to use qsort, the only thing that makes qsort common is that it is available in the standard library, but there are other libraries that provide a faster approach, e.g. SGLIB[0] uses a macro-based approach where the code and comparison can either be inlined with the code or define functions for sorting specific types[1]. There are other libraries that do the same, another one was posted here recently. And of course, if needed, it can be implemented by the programmer. IMO the issue with the given Postgres example isn't that it is written in C therefore it is slow, it is why it doesn't use all of C's features to make it faster (assuming there is a real performance issue here - it is very possible that the Postgres authors didn't consider it a real issue until now). [0] http://sglib.sourceforge.net http://sglib.sourceforge.net [1] http://sglib.sourceforge.net/doc/index.html#array_exam http://sglib.sourceforge.net/doc/index.html#array_exam
  • gpderetta 4y ago
    You can certainly do static polymorphism with macros in C, it is just very painful and unpleasant.
    • badsectoracula 4y ago
      You don't need to do it all the time - or at all - just for the few things that can be performance sensitive (assuming the only reason you'd care is about performance and not, e.g. type safety) and that after you've actually figured out there is a performance issue that can only be solved with such an approach. After all while the linked article's author seem to present it as a problem that it took 25 years for this to be fixed, another way to see it is that it took 25 years for this to be an issue for someone to bother enough to try and fix it.
  • deleted 4y ago
    [deleted]
  • RcouF1uZ4gsC 4y ago
    > IMO the issue with the given Postgres example isn't that it is written in C therefore it is slow, it is why it doesn't use all of C's features to make it faster I think the issue the author is pointing out is that, in the real world, this real-life (fairly obvious) performance improvement was enough of a pain in C, that it was not done for 25 years. In languages with generics, this improvement would have come for free. With C, yes you can do the improvement, but you have to do it by hand, and you have now to maintain and debug multiple versions of sort.
• jstimpfle 4y ago
  Whenever I read a post with this premise and the first thing that pops up is qsort, I instinctly call BS. (Sorry to the author, no offense meant, I didn't read the post). qsort is the prime example why (when!) generics do not matter. Half of the time if you need to sort, you're doing something wrong and the data should already be sorted (that's a sort in constant time). If that is not the case, but performance matters (which is quite unlikely by itself, since sorting is probably not where your program spends its time), then it is extremely likely that it's easy to write a much quicker sort than poort std::sort by taking advantage of the context. For example, some bucket sort which you could say runs in linear time. The time spent waiting for bloated C++ templates to compile can instead be used to implement a sort routine that beats std::sort for the specific situation, and to improve on it 12 times over. There is yet another point that is frequently heard, which is that compilers can inline function pointers if the "qsort" is defined as static inline. I'm only not sure how to guarantee that the inlining is performed. To me this goes mostly to show that most people that whine about generics & performance don't know a lot about performance.
  • vitno 4y ago
    This comment really misses the point of the post and kinda just feels like you have an ax to grind about sorting. This feels like when people say "don't worry about memory safety, just don't write bad code". "don't worry about generics, just don't sort" Generic sorting is something all programmers are familiar with so it makes good examples.
    • jstimpfle 4y ago
      It's not a good example if it isn't a realistic situation. Kinda like the Dog->Animal inheritance hierarchies to prove why OOP syntax is required.
      • ncmncm 4y ago
        OOP syntax is not in fact required, and such hierarchies are not in fact presented for that reason. They are used to illustrate a concept using a familiar subject. OOP is rarely the right way to organize a program, but almost any sufficiently large program has one or more subsystems that map naturally to OOP. A language that supports it is helpful in those places. Saying you could code the same thing without the feature wholly misses the point: of course you could, but it would be more work, and there would be more places to make mistakes. The same applies to any powerful language feature. Where it is useful, using it helps. Where it is not useful, another may be. Languages lacking powerful features make the programmer do more work, leaving less time and attention to make the program, or other more important programs, better.
• xedrac 4y ago
  I like how C++ gets the verbose template parameter name of RandomAccessIterator (repeated 3 times), while Rust gets T. It's sort of like he's saying, "if you choose to use C++, this is the sort of muck you'll have to deal with." He's not wrong, it's just funny.
  • veilrap 4y ago
    The C++ code could have also just have been `T`. It's a bit odd of a comparison because `RandomAccessIterator` is just a name the author chose for the template typename.
    • zerocrates 4y ago
      I think that's what the person you responded to was saying actually, that the author specifically chose a verbose template parameter for the C++ examples.
      • ncmncm 4y ago
        That author missed the significance of a detail that illustrates a major difference in the expressive power of C++ vs. Rust.
        • tialaramex 4y ago
          You've confused RandomAccessIterator (a perfectly reasonable name for a Rust trait, but not really in the usual style of the C++ standard library) for std::random_access_iterator an actual concept defined in C++ 20 std::random_access_iterator like most of its fellows in C++ 20 is largely duck typed, there's a semantic "model" provided, but this is not enforced anywhere and your compiler will actually accept completely bogus types so long as the syntax matches. The standard washes its hands of the consequences by saying that if you don't obey the model your program is not valid C++ and the compiler is not expected to detect that and tell you about it.
          • 4y ago
• AtNightWeCode 4y ago
  Wasn’t performance the argument against generics in GO? Were they just obstinate?
  • oconnor663 4y ago
    I think complexity was the main argument against, and the majority opinion around performance was that the status quo was good enough. Unless you meant compile-time performance, in which case yes that was another argument against.
    • AtNightWeCode 4y ago
      Thank you. Now I remember. It was compile-time performance not the actual performance.
  • deleted 4y ago
    [deleted]
  • topspin 4y ago
    A key driver of Go design was compiler performance. Generics make the compiler more complex, use more memory, etc. and presumably require a less performant compiler. I don't know what the implications are for Go with generic types. Either they've convinced themselves that a fast generic capable compiler is possible or the the compiler performance goal is no longer the high priority it once was.
• munificent 4y ago
  I agree wholeheartedly. If your language has static types but no generics, it's akin to supporting functions but not parameters. Static types without generics are like the `GOSUB` of type systems.
  • Konohamaru 4y ago
    What are static types?
    • munificent 4y ago
      A type system. Statically typed languages are C, Java, C#, TypeScript, Swift, Kotlin, etc.
      • Konohamaru 4y ago
        C doesn't have types, they just have word decorations you sprinkle on parameters and variable declarations.
• haberman 4y ago
  Not mentioned: the type-specialized code is larger in code size, which can cause its own performance problems due to icache. A virtue of C, in my opinion, is that it's very difficult to accidentally bloat the code. C code tends to produce smaller binaries, while leaving the option of expanding performance-critical code sections with macros in cases where it is beneficial. It's much more difficult to take a heavily-templated C++ binary and shrink code size in the cold parts of the binary (which is probably most of the binary).
  • bestouff 4y ago
    Same thing in e.g. Rust: you can either monomorphize (expand code for each generic it's used with), use dynamic dispatch via a vtable or (with help from a crate) dispatch via an enum. Each solution has its tradeoffs, you are empowered to choose.
    • dralley 4y ago
      Granted, "you" does mean you, in practice if you're using dependencies, everyone else has likely chosen static dispatch.
  • kaba0 4y ago
    Though C macros are so bad they give the whole term a bad name. You might as well write a sed script for “macro expansion” instead of what the preprocessor does.
    • Koshkin 4y ago
      Except I do not think you could (not easily, anyway), the C macro processor is a rather sophisticated piece of code.
      • anon25783 4y ago
        Is it really though? I feel like I could implement a C macro preprocessor in Python in like two or three days.
• flohofwoe 4y ago
  Minor nitpick: if the implementation of qsort() would be visible to the C compiler (for instance if it would be defined as inline code in stdlib.h, or with a statically linked libc and LTO), the compiler would happily "stamp out" a specialized version of the function, just as std::qsort() does in C++ (assuming the right optimization settings). After all, "zero cost abstraction" (aka "optimizer passes") works just as well in C as in C++ ;) The actual advantage of generics isn't performance, but less (manual) code duplication.
  • throwawaymaths 4y ago
    I think "just as well" elides maintainability... I would not want to have to debug a generic sorter written in c preprocessor.
    • flohofwoe 4y ago
      In the case of qsort() at least, there wouldn't be "preprocessor generics" involved, because the comparison is done in a user-provided callback function. But both the comparison function and the qsort implementation must be visible to the compiler (or in case of LTO: the linker) for the "auto-specialization" (via the optimizer) to kick in. It's a bit brittle of course to depend too much on the optimizer, but the whole idea of "zero cost abstraction" in C++ also puts a lot of trust into the optimizer passes.
    • randbox 4y ago
      The only preprocessor code required for writing 'static inline' header functions is "#pragma once". Inline functions look like normal functions.
  • adrianN 4y ago
    I still see a call instruction here https://godbolt.org/z/GWKdaoEG4 https://godbolt.org/z/GWKdaoEG4. Am I doing something wrong?
    • flohofwoe 4y ago
      Try to define the find() function as inline or static (but in this case the optimizer is actually too aggressive for this example and resolves the entire function call into a constant).
• MrYellowP 4y ago
  Please excuse me, I have actually serious questions: Are Generics a solution to a problem caused by programming in OOP? Can someone explain what people did to solve these problems before someone came up with generics? Thank you!
  • kaba0 4y ago
    No, functional languages also have generics. It is a type system feature, not related to OOP. Maybe the best example of a language without generics is C. In short there are 3 solutions to counter the lack of generics: copy-paste the same code multiple times with minor changes, make this copy-paste automatic with macros, or circumvent the problem by further abstraction. Let’s say you want to create a vector data structure that can grow. It is not a hard thing if you know the size of each element, so you can trivially write it for, say, ints. Now you want to reuse your logic for your custom structs that have a different size - the only change you would have to do is replace the element_size constant and repeat the whole thing with a different name (first solution). You might try to write some ugly hack with C’s pre-processor macro to generate this thing for you by an easier to use wrapper, or you could just implement a wrapper that has a next, prev pointer and use a linked list structure (with very bad performance compared to storing the elements next to each other in an array). C code often uses the third option due to the inconvenience of the first 2, which would be solved by generics.
    • MrYellowP 4y ago
      Aahhh, now I get it! So you basically write code for "one size fits all" for the programmers convinience, at the cost of performance/general efficiency? Thank you for the response!
  • wvenable 4y ago
    > Can someone explain what people did to solve these problems before someone came up with generics? Like many things in programming, when your language didn't have a feature you just did it yourself. You didn't have one sort() method you had a different one for integers, floats, strings, etc. Or you used other language features that could accomplish the same thing only a little messier.
• jmull 4y ago
  I agree with the conclusion (generics good) but the argument's not good. All your 25 year-old projects will have performance bottlenecks to the extent you don't look for and address them. The idea here that if you use generics your hot-path inner loops will be automatically optimized is nonsense. Yes, here and there you may get lucky -- the generics will exposes some code to an optimizer which will generate some great instructions without any extra work by you. But while shaving a few bottlenecks off it nice, if your goal is performance, the bulk of the work is the same: you'll still have to consistently profile and optimize your code.
  • dgb23 4y ago
    Thank you. I have little experience with systems programming, but the article seemed very off to me.
• _ink_ 4y ago
  Wouldn't the Java equivalent be? public static <T> void sort(T[] array);
• pcwalton 4y ago
  I absolutely agree that modern programming languages need generics, but this particular issue with qsort is only a problem if you're not using link-time optimization (LTO). If you care about performance, you should be using LTO (all the FAANGs use it extensively, for example). And if you do use LTO, then the call overhead of qsort is eliminated via inlining. As an example, here's musl's qsort() implementation paired with a use in Godbolt. (I couldn't actually use LTO on Godbolt because it doesn't LTO the standard library, but the effect would be the same.) Note that there are no call instructions at all and the compareme() function is completely eliminated by the optimizer: https://godbolt.org/z/6W8Wxf6xP https://godbolt.org/z/6W8Wxf6xP
  • gpderetta 4y ago
    For LTO, you also need to statically link with your libc which is seldom done (do FAANGs do it?). Or write/duplicate qsort in your own library, which is more likely.
• dan-robertson 4y ago
  To say something that’s maybe obvious: generics don’t seem so necessary for languages with dynamic types. (Caveat: I definitely remember wanting to express parameterised types in Common Lisp but I was probably doing something wrong). I’d argue that memory safety feels like more of a requirement but there are plenty of new languages which don’t have it. The performance argument (for generics in statically typed languages) also feels weak to me. Firstly, you can get lots of the same value of generics using polymorphism in a language like ML. E.g. sort might have a type like: type ordering = LT | EQ | GT sort :: ('a -> 'a -> ordering) -> 'a array -> 'a array Which reads as ‘sort takes a function to compare things of some type 'a, and an array of such things, and gives you a (sorted) array of those things.’ You can get type safety enforcing correct call sites (ie no sorting an array of strings with int comparison) and type safety in the implementation of the sort function however this could be implemented with (machine) code generated for the sort function only once rather than a separate function for each different type it’s used with. Indeed this is what you’ll get with the classic OCaml compiler. The thing you would want for performance is either sufficient inlining or generics which generate new code for each call. So it seems that performance is not a necessary consequence of that sort of code generation. (Also you will get worse type checking with something like C++ templates because they are type-checked where they’re expanded rather than where they are created). Secondly, this style of generics may lead to code size bloat which may lead to poor performance. Sure it is nice if you can speed up the functions in your critical path by 6% but if you have a big program doing lots of things, the increased number of cache misses/reads from having more code may slow you down. It’s maybe not great if e.g. you have a different function to peek inside a future/extract the value for each different thing you’d put in it, but that function would likely be inlined either way so isn’t a great example.
• ArrayBoundCheck 4y ago