[HN Gopher] Modern programming languages require generics
___________________________________________________________________
Modern programming languages require generics
Author : wagslane
Score : 184 points
Date : 2022-05-24 13:58 UTC (9 hours ago)
(HTM) web link (ayende.com)
(TXT) w3m dump (ayende.com)
| lifthrasiir wrote:
| 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 wrote:
| 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 wrote:
| C++ can be plenty faster than C, not in small part due to its
| templates.
| eterevsky wrote:
| 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 wrote:
| 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 wrote:
| 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.
| lifthrasiir wrote:
| Not every code is written with performance in mind. In
| fact, most aren't. This alone gives much leeway for
| dynamic languages; if you can make more performant
| program easier to write, they can pay off even when their
| maximum performance is limited (this is my definition of
| "reasonably performant"). The exact amount of leeway will
| of course depend on circumstances but I guess 10x is a
| fair estimate, which many JIT implementations can reach
| ---not just crazy beasts like JS engines.
| AtNightWeCode wrote:
| Wasn't performance the argument against generics in GO? Were they
| just obstinate?
| [deleted]
| oconnor663 wrote:
| 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 wrote:
| Thank you. Now I remember. It was compile-time performance
| not the actual performance.
| flohofwoe wrote:
| 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 wrote:
| I think "just as well" elides maintainability... I would not
| want to have to debug a generic sorter written in c
| preprocessor.
| randbox wrote:
| The only _preprocessor_ code required for writing 'static
| inline' header functions is "#pragma once". Inline functions
| look like normal functions.
| flohofwoe wrote:
| 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.
| fweimer wrote:
| glibc does exactly this for bsearch. The difference with C++ is
| that the specialized function (bsearch or qsort) does not
| receive vague linkage, so it is not going to be deduplicated by
| the link editor. For bsearch, the code size increase is
| probably not a problem, but qsort tends to be much larger.
| Basically, intra-procedural constant propagation plus inlining
| into qsort is very beneficial, but inlining the specialized
| qsort itself is probably not such a great idea. Presumably LTO
| with profile feedback could help here, but striking the right
| balance is going to be difficult (as is with C++, which tends
| towards code duplication, despite vague linkage and link
| editors that perform identical code folding).
|
| I'm not sure if specialization is a good argument for generics.
| Not everyone implements generics through full
| specialization/monomorphization, and then the performance
| benefits are not much more likely to emerge than with function
| pointers or vtables. And many JIT compilers can effectively
| specialize code involving indirect calls.
| layer8 wrote:
| Not only the implementation of qsort would have to be visible
| to the compiler, but also the implementation of the comparison
| function, which may be defined in a separately compiled module
| or passed around dynamically as a function pointer (as might
| qsort itself, potentially).
|
| > The actual advantage of generics isn't performance, but less
| (manual) code duplication.
|
| Or type safety, since code duplication will often be shunned.
| And the benefit of type safety is there regardless of whether
| the generics implementation performs specialization.
| adrianN wrote:
| I still see a call instruction here
| https://godbolt.org/z/GWKdaoEG4. Am I doing something wrong?
| flohofwoe wrote:
| 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).
| adrianN wrote:
| Okay, but as far as I know "inline" is just a suggestion
| for the compiler. Depending on the complexity of the
| function or the phase of the moon the compiler can choose
| not to inline it. I wouldn't want to rely on that for a
| critical piece of my performance.
| evmar wrote:
| `static` also allows it to optimize, and it's more of a
| code hygiene thing. Your original code as written
| unintentionally defines `find` as a function that must be
| preserved (as a separate function) into the compiled
| output, and `static` undoes that.
| flohofwoe wrote:
| True, that's what I mean with depending too much on the
| optimizer (in a sibling comment). But IME the threshold
| for inlining code is surprisingly big (which of course
| also has a downside: potential code bloat).
|
| I added a little fix which prevents the compiler from
| discarding the result completely (just by going through
| __builtin_printf()):
|
| https://godbolt.org/z/W93WrhbaE
|
| PS: another minor tweak (make the comparison function
| static, so that no extra copy is included in the compiler
| output):
|
| https://godbolt.org/z/5TTM4x193
| hermitdev wrote:
| > Am I doing something wrong?
|
| Yes, you just compiled C code as C++. Actually write it as
| C++ (get rid of the void* mostly) and your program becomes a
| constant time evaluation: https://godbolt.org/z/5fedo8s5q
| uecker wrote:
| So here is my C version:
|
| https://godbolt.org/z/zTe8jocsE
|
| Now tell me I need generics for this to get optimized.
| (Generics are useful for type safety, which you can add using
| macros in C, but this is then ugly).
| SubjectToChange wrote:
| You might as well argue that (speculative) devirtualization
| negates the overhead of virtual functions in C++.
|
| >Now tell me I need generics for this to get optimized.
|
| Generics are explicit and reliably optimized. Implicit
| function pointer optimization is non-obvious and optimized
| unreliably.
| jstimpfle wrote:
| 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.
| japhib wrote:
| You should probably read the post first, my dude.
|
| > Half of the time if you need to sort, you're doing something
| wrong and the data should already be sorted
|
| OP is literally talking about the C implementation of Postgres.
| He probably needs to sort.
| jstimpfle wrote:
| I hadn't known that we're on such close terms, my friend.
|
| Seems like this case is falling in the other half then.
| jyounker wrote:
| He knows the information about the author because he read
| the article.
| sophacles wrote:
| Why can't postgres just get it's data in a pre-sorted way
| tho?
| sicp-enjoyer wrote:
| Stable sort and binary search is the bread and butter of
| pretty much every database operation.
|
| When you bulk insert into indexed columns, it sorts the
| inserted data and merges that with the existing index. If
| you do joins on non-indexed columns it often sorts the
| intermediate results.
| jstimpfle wrote:
| Only the least technical among many possible reasons: it
| cannot know in advance the row ordering that is requested
| by the user.
| vitno wrote:
| 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 wrote:
| 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 wrote:
| 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.
| jstimpfle wrote:
| I wasn't saying there can't be a good way to put a
| feature to use. And, like any programmer that is
| maintaining a level of pride, I'm aware I am constantly
| looking for reasons why certain features aren't needed or
| are even bad in the global picture, at least in a given
| context. Looking for a minimal set of axioms to build the
| world on does make sense. Language feature can be seen as
| axioms in the sense that it's hard or impossible to break
| them down, since they're hidden in the compiler.
|
| Regarding OOP syntax specifically, let us agree that it
| is a question of religion if writing foo.bar() instead of
| foo_bar(foo) is really a huge saving of work. There are
| numerous counter-arguments (language-specific ones as
| well as more general ones) why it could be not, and could
| in fact be detrimental.
|
| I disagree with the view that using any feature to
| quickly get something done leaves more time to make the
| program better. In my view, less focus on syntactic
| superficialities like OOP method syntax, and premature
| optimizations like using std::sort, leaves more time to
| focus on what really matters, to understand what a
| program does and needs to do on a global scale, and it
| holds me back less waiting for slow builds.
|
| All of that is pretty subjective, and there are certainly
| good examples for many different approaches, and
| naturally one is most familiar with those that one likes
| personally. The important thing is to be happy and be /
| feel productive.
| melissalobos wrote:
| > most people that whine about generics & performance don't
| know a lot about performance
|
| Really it is almost everyone who doesn't know a lot about
| performance. Any modern programming language is targeted not at
| an expert, but a beginner(look at Rust which is supposed to be
| relatively difficult, yet is quite quick for people to pick up
| in my experience).
|
| Languages should be able to be performant, even when used in
| poor ways. No matter what, people won't presort their data,
| since it likely comes from some database or csv file or json
| response or who knows what. So a language should be trying to
| accommodate that use case.
| jmull wrote:
| 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 wrote:
| Thank you. I have little experience with systems programming,
| but the article seemed very off to me.
| Zababa wrote:
| Discussed yesterday, 24 comments
| https://news.ycombinator.com/item?id=31475765.
| nemo1618 wrote:
| 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.
| ragingglow wrote:
| I completely disagree. Putting builtins on some special
| pedestal and demoting user-defined classes and functions is
| always a mistake IMO. I also don't see how this is a reasonable
| approach even in the cases you mention. If map is polymorphic,
| but I can't define polymorphic classes myself, it seems
| impossible to define classes that can hold arbitrary maps. So I
| can't even wrap map.
|
| Also, if I'm reading https://go.dev/tour/moretypes/15
| correctly, append is a variadic function and not a polymorphic
| function. That's something very different.
| turminal wrote:
| > Also, if I'm reading https://go.dev/tour/moretypes/15
| correctly, append is a variadic function and not a
| polymorphic function. That's something very different.
|
| It is both variadic and polymorphic.
|
| > Putting builtins on some special pedestal and demoting
| user-defined classes and functions is always a mistake IMO.
|
| There is a line of thought in programming language design
| that claims everything should be user defined, but too much
| customization of everything inevitably leads to a lot of
| fragmentation, subtle incompatibilities and lots of ways to
| solve the same simple problem.
|
| Avoiding all of these issues is an important part of go's
| reasoning behind some of their design choices and the
| proposed idea could probably fit that quite well.
| dhagz wrote:
| 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 wrote:
| 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 wrote:
| Generic solutions are certainly not "the remaining 10%".
| lawn wrote:
| > Providing a generic `sort`, `reverse`, and a few others would
| cover 90% of the cases mentioned in every "Go needs generics!!"
| article.
|
| That's only because the articles would be too long otherwise.
|
| When I worked in a language without user defined generics I
| missed them all the time, and now when I work with Rust I use
| them all the time.
| eternalban wrote:
| Yes to reverse, but how would a builtin sort generically
| address comparability?
| jerf wrote:
| "What Go 1.0 didn't have was user-defined generics."
|
| If you sit down and carefully write out the _use cases_ for
| generics, which extend well beyond "parameterized data types",
| you'll note that Go interfaces cover a lot of them reasonably
| well, which is how it has been a viable language for versions
| 1.0 - 1.17. While this is an unpopular opinion, I don't really
| consider 1.18 to have "added" generics so much as _completed_
| them. (As evidence, consider how important "interfaces" still
| are in generics, and I can attest from personal experience with
| helping people that there's a lot of people who try to fire
| "generics" at a problem when they just need interfaces.)
|
| I say this in support of the original post. Otherwise one must
| reconcile how Go could be successful "without generics"; my
| suggested resolution is that it shipped with "bad" or
| "incomplete" (more charitably) generics rather than _no_
| generics. Compare programming in Go with programming in C and
| the differences become very clear. There 's a reason so many
| people were able to smoothly transition their code bases from
| Python to Go, for instance, which a view of Go in which it
| literally has "no" generics finds hard to account for. You need
| more than just "maps" and "slices" to do that successfully.
| HL33tibCe7 wrote:
| Which other built-in generics should have been added?
| eweise wrote:
| What's wrong with opening the door to user-defined generics?
| formerly_proven wrote:
| > 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.
| mrighele wrote:
| 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/ [2]
| https://www.graalvm.org/python/
| amenghra wrote:
| 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 wrote:
| 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?
| charcircuit wrote:
| >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.
| taeric wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| This has little (nothing?) to do with generics, though. This is
| an example of function (name) overloading.
| tialaramex wrote:
| 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 wrote:
| 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).
| zwieback wrote:
| Yes, seems like Java generics are an argument against the
| "generics allow optimization" argument. Maybe I misunderstood
| what he was trying to say.
| mumblemumble wrote:
| 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 wrote:
| 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 wrote:
| 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.
| lifthrasiir wrote:
| 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.
| kaba0 wrote:
| 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 wrote:
| 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 wrote:
| 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)
| malfist wrote:
| Features added after launch doesn't make something an
| afterthought. Java generics are a key part of the language.
| switchbak wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| marginalia_nu wrote:
| 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 wrote:
| 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.
| mrighele wrote:
| The example you provide has little to do with generics,
| but how inheritance works.
|
| In particular if you override a method in a derived
| class, you're allowed to return an instance of a more
| specific class (in your example, Bar is an Object so it
| is fine). At runtime, your example is equivalent to
| something like interface Supplier {
| Object get(); } class Foo extends
| Supplier { Bar get() { return new Bar(); }
| }
| marginalia_nu wrote:
| 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 wrote:
| 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.
| marginalia_nu wrote:
| If you consider this example: class
| Base<T> { T f() { return null; } }
| class A<T2> extends Base<T2> { @Override
| T2 f() { return null; } } class B extends
| Base<Integer> { @Override Integer
| f() { return null; } } class C {
| Integer f() { return null; } }
|
| Base has a parameter T which is erased in Base.
|
| A has a parameter T2 which is erased in A.
|
| B because B is not a generic class and nothing is erased
| from B.
|
| Base has the same shape as A; B has the same shape as C.
| bumper_crop wrote:
| The JVM still doesn't know about generics. The
| explanation you provided is entirely at the compiler
| (javac) level, and the JVM is still oblivious to it.
| There is no special dispatch, or optimization. At best,
| you could say there is support in the Java standard
| library, but not in the JVM or hotspot or anything from
| running "java".
|
| An easy way to verify: Are generics in Clojure, Scala, or
| JRuby the same as Java (the programming language)?
| dcminter wrote:
| For most purposes, but there's a little in reflection and
| so forth. For example:
|
| https://docs.oracle.com/en/java/javase/17/docs/api/java.bas
| e...()
|
| Edit: sibling comment by cogman makes the case more
| thoroughly.
|
| Edit: also HN mangles the link to Class.getTypeParameters()
| Smaug123 wrote:
| Per https://news.ycombinator.com/formatdoc, put it in
| angle brackets. Maybe this works? <https://docs.oracle.co
| m/en/java/javase/17/docs/api/java.base...>
| dcminter wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| _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.
| layer8 wrote:
| Collections.sort() just copies the list into an array, sorts
| the array, and copies the sorted elements back into the list.
| So it also just sorts an array under the hood. To eliminate
| the temporary array (at least for ArrayList), the List#sort()
| method was added in Java 8.
|
| Arrays are usually still preferred over collections in the
| case of primitive types (int[] etc.).
| munificent wrote:
| 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.
| duped wrote:
| 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.
| _ink_ wrote:
| Wouldn't the Java equivalent be?
|
| public static <T> void sort(T[] array);
| haberman wrote:
| 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 wrote:
| 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.
| jjtheblunt wrote:
| curious what you mean by
|
| > the type-specialized code is larger in code size, which can
| cause its own performance problems due to icache.
|
| since IIUC you mean the alternative would be essentially non-
| reified types, so the icache would involve more frequent
| branches, thus blowing cache in general, even with branch
| prediction.
|
| anyway i'm pretty sure i'm missing your point, so figured may
| as well ask.
| kaba0 wrote:
| 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.
| abainbridge wrote:
| I think the case against the C preprocessor is overblown.
| What's the worst problem C macros have caused you? I've been
| programming C for 27 years and I can't really think of them
| causing any bugs in my programs. The worst thing for me is
| that #defines don't show up in the debug info.
| colonwqbang wrote:
| C programmers tend to reach for the preprocessor in cases
| where other tools would have been more appropriate. In
| particular, #ifdef. If you haven't experienced this then
| maybe you've worked with people that have uncommonly good
| taste.
|
| I agree there's nothing particularly terrible about the
| preprocessor as such, if used tastefully. Especially if you
| compare it to other macro engines like maybe TeX, CPP
| strikes me as quite simple and clean.
|
| Even newer languages like Haskell choose to adopt it after
| all.
| Koshkin wrote:
| Except I do not think you could (not easily, anyway), the C
| macro processor is a rather sophisticated piece of code.
| badsectoracula wrote:
| 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
|
| [1] http://sglib.sourceforge.net/doc/index.html#array_exam
| [deleted]
| RcouF1uZ4gsC wrote:
| > 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.
| cozzyd wrote:
| Well, as parent noted, you can use sglib, or implement your
| own thing in a similar manner (it's not that hard, sglib.h is
| very readable...).
| msbarnett wrote:
| > 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).
|
| Right, but that's kind of missing the author's point, which
| isn't "things that are written in C are slow" so much as
| "because C lacks generics and has a relatively-inefficient
| standard library implementation based on function pointers,
| _most implementations_ do not take the extra steps of 'using
| all of C's features' to do something faster (because it's a lot
| of work, and the standard implementation exists)".
|
| It's mostly just an argument that generic-lacking languages
| make it easier to do something slower than something faster,
| and most people and projects follow the path of least
| resistance. That there are more efficient implementations
| available if you sink more effort into it isn't in dispute.
| gpderetta wrote:
| You can certainly do static polymorphism with macros in C, it
| is just very painful and unpleasant.
| badsectoracula wrote:
| 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.
| jimbokun wrote:
| 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 wrote:
| 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 wrote:
| I'm still surprised that generics increase performance. I also
| don't fully understand how.
| taeric wrote:
| Anytime you can move a choice from runtime to compile time,
| it has the ability to speed up runtime. Such that if a lot of
| what your sort routine is doing at runtime is finding out
| what the type of the objects being sorted is, then moving
| that to a choice at compile time can recover all of that
| time.
|
| Note, this is not just generics. Java could use overloading
| for years before generics to get similar benefits. Common
| LISP has type annotations that can give similar benefits.
| Generics is just a much easier/stronger to use construct for
| this in many cases.
| duped wrote:
| Essentially without generics, any kind of polymorphic code
| needs to use dynamic dispatch. For example, if you add a
| generic sort() function for collections, you would need to
| lookup the comparison function for any arguments at runtime.
| Generic programming - be it through type parameters, ad hoc
| polymorphism, or whatever - allows a language implementation
| to know what that comparison function is at compile time and
| inline it accordingly. This is true for all kinds of things
| you may want to do generically. Sorting, layout of objects,
| iteration, etc.
|
| Ultimately generic typing is a way of better expressing the
| constraints of a program to a compiler, which means the
| compiler can do a better job of generating code for specific
| instances. The downside is that the compiler needs to
| generate code explicitly for each concrete instance of a
| generic function or type, which means that it takes more
| compile time and code size is larger.
|
| Edit: I'd also like to point out that JIT compilers and
| sufficiently-smart AOT compilers _can_ do this sort of
| inlining if they can prove that for any combination of run
| time types passed into a sort() they have the same comparison
| function and inline it as needed. That said it 's the same
| (or higher) complexity as a generics system, with more
| pitfalls (for example, if they can't _prove_ it but make a
| guess the sort function never changes, then get the guess
| wrong, they have to de-optimize).
| b0sk wrote:
| the post goes in detail.
|
| Essentially, imagine you have custom routines for your ints
| and floats and your language doesn't support generics. You'll
| have a code like this if type is INT:
| answer = optimizedRoutineForInt(); else type is FLOAT:
| answer = optimizedRoutineForFloat();
|
| This happens at run-time. There's an overhead.
|
| With generics, there's zero overhead. Your code will look
| something like answer =
| optimizedRoutine<Type>();
|
| and if optimizedRoutine<Float> can be inlined at this site,
| there are no conditions or jumps in the code.
|
| The post goes in detail about how for sorting, this sort of
| comparison function is called _so frequently it has a massive
| impact on performance_
| veidelis wrote:
| ..this comparison function of sort..
| mcluck wrote:
| The ultra short version of what he is saying is that generics
| allow you to provide information to the compiler that enables
| inlining. So instead of doing something like this (pseudo
| assembly) PUSH x PUSH y
| CALL compare CMP x y POP
|
| You end up with CMP x y
|
| Of course this will vary based on the type that you're
| optimizing for but in all cases you're removing the need to
| push and pop the stack for every comparison. I'm not smart
| enough to talk about other optimizations enabled by generics
| though.
| jacksnipe wrote:
| 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 wrote:
| 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.
| jacksnipe wrote:
| You're right, inlining is the actual key. My comment is a
| bit jumbled.
| xedrac wrote:
| 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.
| ncmncm wrote:
| As of C++20, with "Concepts", that name is not just a
| placeholder. It means something that enables the compiler to do
| work for you that Rust cannot. The most trivial of that work is
| to check that the type provided implements a comparison
| operator, which mostly affects error messages if you pass a
| type without, but you can use it to make types pick up a great
| deal more reponsibility.
|
| It is not often mentioned on HN that whole swathes of
| functionality modern C++ coding relies on are entirely missing
| from Rust. Clearly, people can get along without powerful
| features -- important programs are coded even in C -- but it is
| a great deal more work. One consequence is that C++ and, to a
| degree, Rust programs are faster than programs coded in weaker
| languages, simply because more time is available to pay
| attention to performance, and any such attention to a library
| may help many more programs. Weaker languages are simply unable
| to express usability improvements and optimizations you would
| like to capture in a library.
| oconnor663 wrote:
| > check that the type provided implements a comparison
| operator
|
| If I understand correctly, this is done with traits in Rust.
| In this case, the PartialOrd and Ord traits. More elaborate
| use cases for traits cover things like "is this type safe to
| send between threads" and "does this type have a statically
| known size on the stack".
| avgcorrection wrote:
| Presumably they intended to say that the (1) cplusplus
| thing can express something that Rust cannot, and (2)
| here's an example of Thing. But then they didn't properly
| delineate the two things so that it might come off as if
| (2) is an argument for (1), but really (1) just talks about
| Thing in isolation and not as a comparison to Rust... The
| example was just a standalone example, unrelated to Rust.
| veilrap wrote:
| 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 wrote:
| 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 wrote:
| That author missed the significance of a detail that
| illustrates a major difference in the expressive power of
| C++ vs. Rust.
| rahimiali wrote:
| 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?
| ncmncm wrote:
| That misses a fundamental point: that is about equivalent to
| textual substitution. With enough inlines, the compiler can
| patch together a specialized version of the function applied
| with that comparator.
|
| What it can't do is vary details of the implementation, at
| compile time, according to properties of the types operated on.
| C++ can do this. Rust can, to a degree. Go cannot, because it
| doesn't understand much about types. C macros cannot, because
| the macro system has no conception of types at all. The C
| optimizer can apply what it knows of types, but you have no way
| to tell it any more than it can puzzle out for itself.
|
| If you are not used to a language that really supports strong
| types, you probably don't understand how much of programming
| work is offloaded onto the type system when using such
| languages. The C-grade "type checking" such languages provide
| is just the most trivial possible use of compile-time types. A
| powerful type system makes a language able to do automatically
| what you almost always cannot afford to do at all in a language
| without.
| unwind wrote:
| The compare function is passed by value (like all things in C)
| and the preprocessor is not smart enough to find the code.
| brabel wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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/ might be useful for this exercise.
| jjnoakes wrote:
| Did you reply to the right comment?
| derriz wrote:
| There was a C library - posted here but I cannot remember the
| name - which used the preprocessor to avoid invoking a
| function call per comparison. You'd use it something like
| this:
|
| #define SORT_ELEMENT_TYPE int
|
| #define SORT_COMPARE(a, b) sign(a - b)
|
| #include "specialized_sort.h"
|
| And the header would define a function with the following
| signature:
|
| int sort_int(int[] a, size_t n);
| KapKap55 wrote:
| Maybe not it, but STC (https://github.com/tylov/STC) and
| CTL (https://github.com/glouw/ctl) both use this define
| method for creating data structures and linking up compare
| functions for them.
| randbox wrote:
| It's not necessary to use macros. Just make both the sort
| function which the comparison function is passed to, as
| well as the comparison function itself, both "static
| inline". The compiler is smart enough to figure it out.
| jhallenworld wrote:
| I've written code just like this. Another option is to make
| the entire sort function a C macro. This would be feasible
| for something simple like quicksort.
|
| But generics provide another benefit: in theory with them,
| the compiler should be able to determine that two high-
| level types are actually the same machine type, so in the
| above example, SORT_ELEMENT_TYPE int and long would not
| generate duplicate code on many machines.
| randbox wrote:
| If _both_ the comparison function as well as the sort
| function which the comparison function is passed to are
| declared 'static inline' and available in a header, the
| compiler is smart enough to figure it out and inline the
| code, provided optimizations are turned on.
| jjnoakes wrote:
| Why is this limited to the preprocessor? I imagine the
| compiler proper could inline the compare function parameter
| into the qsort implementation body in the typical case, at
| the qsort() call site. (Assuming qsort's implementation was
| in a header, as the original comment posited).
| syockit wrote:
| You're right. I tried it here
| https://godbolt.org/z/457dYWfq5 and if the generic function
| is visible to the call site and inlineable, then the
| compare function can be inlined too. I didn't know this, I
| had always thought that the semantics of function pointer
| prevented this from being achievable!
| unwind wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| Also possible: return (a > b) - (a < b);
| layer8 wrote:
| 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 wrote:
| 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 wrote:
| I think there were already much better models to follow than
| C++, in ML for example.
| Jtsummers wrote:
| 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 wrote:
| 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
| DANK_YACHT wrote:
| And yet Java and Go are both wildly successful languages. While
| lack of generic support may be a mistake, it's clearly not a
| critical one.
| ModernMech wrote:
| Both Java and Go are developed by mega corporations though.
| Hard to disentangle their successes from that. It's not hard
| to be successful (when success is measured as adoption) when
| you literally can't fail due to the giant pile and of never-
| ending cash and army of developers fueling your growth. Even
| if your language is terrible people will adopt it, if for no
| other reason than Google or Oracle are behind the project.
|
| If Oracle were to disappear tomorrow I imagine Java would
| persist for quite a while as it's so embedded by now. It's
| _the_ introductory language in schools across the US, so it
| 's not going anywhere for now.
|
| Go on the other hand I don't think would last very long
| (maybe a decade?) if Google decided to divorce themselves of
| the language, as it doesn't have the installed userbase of
| Java, but that's just my opinion. Who knows what would
| happen.
| layer8 wrote:
| The question is for how long, if they hadn't added generics
| at some point. There's certainly a lot of pressure e.g. for
| Go to have added generics, and Rust and Swift likely wouldn't
| have been as successful as they are if they didn't include
| generics.
|
| This is anecdotal, but Java 5 adding generics was crucial for
| me to staying with a Java job. Without generics, working with
| generic algorithms and facilities was just miserable, and
| there was great temptation to use code generators based on
| some sort of templated Java as a workaround.
| DANK_YACHT wrote:
| Perhaps it's necessary to add generics to keep users, but
| my takeaway is this: if you have innovative language
| features, then you don't need generics to attract a
| passionate set of early adopters. If you don't have
| innovative language features, people won't use your
| language regardless of generics support.
| layer8 wrote:
| Yeah, as I already said I don't think Rust's borrowing
| semantics would have been quite enough for it to be as
| successful without generics, and Swift as a modern
| replacement for Objectice-C also wouldn't have been quite
| as convincing without generics support (which was a pain
| point in Objective-C).
|
| I can't exclude the possibility of new innovative
| language features outweighing the penalty of not having
| generics (like Go's concurrency support did for a while)
| even today, but I believe it's becoming increasingly
| unlikely (for statically typed languages, obviously).
| marcosdumay wrote:
| Rust's value proposition is being a modern language
| capable of low-level programming. Surely, the low-level
| part is essential, and the borrowing semantics brings it,
| but it wouldn't have much value if it hadn't modern
| features.
| erik_seaberg wrote:
| Just starting with C and adding a borrow checker would
| have had some value (and there are some linters that
| doggedly try to do this). I agree I'd much rather have
| Rust, though.
| tialaramex wrote:
| You can't do Rust without generics at all, they're
| utterly fundamental. Take the for loop. Rust's for loop
| is _literally_ sugar for the infinite loop over an
| Iterator (a generic type) which emits an Option generic,
| with a break for None.
|
| Rust calls such types "langitems" and they're required
| for the core Rust language. An allocator (for heap
| memory) isn't mandatory, fancy file I/O and networking
| aren't mandatory... But the langitems, and thus generic
| types, are mandatory.
| layer8 wrote:
| Rust could conceivably have worked similar to C, where
| you have to cast void* to the correct type. You could
| still have borrowing annotations on such generic
| pointers, similar to how C(++) has const. Having
| borrowing semantics doesn't necessarily imply a general-
| purpose generics feature. Stuff like iterators and option
| types would obviously be different then.
| vlang1dot0 wrote:
| Yes, technically you can do that but it makes no sense
| from a design point of view to have a language that cares
| so much about safety it adds a borrowing system but then
| says "fuck it" to type safety.
|
| You have to have type safety to have memory safety and
| that was the whole point of Rust.
| tialaramex wrote:
| You could build a completely _different_ language with
| some of Rust 's features, if you go back a few years
| before Rust 1.0 there are lots of possibilities, but what
| I was getting at is that Rust itself is much more tightly
| wedded to the generics than many of the languages people
| associate with generics, a "Rust without generics" isn't
| Rust at all.
|
| Even in C++ the generics are a later addition,
| Stroustrup's early 1980s language doesn't have generic
| types, templates were a proposal added to what would
| become the C++ 98 standard and the Standard Template
| Library presents generic types for containers in C++
| years after the C++ language was first popularized.
| layer8 wrote:
| I don't think we really disagree. I was originally
| reaponding to the claim by DANK_YACHT stating that a
| (statically typed) language can be successful without
| having generics as long as it has other sufficiently
| innovative features. As a "counterexample" I hypothesized
| a version of Rust without generics but with the borrow
| checker (arguably the innovative feature most decisive
| for Rust's success) and argued that I would doubt that
| this version would have been very successful, exactly
| because its lack of generics (which I believe aligns with
| what you are arguing). I'm not sure if you're arguing
| that this hypothetical scenario isn't a valid
| counterargument to the original claim I was responding
| to.
| ntoskrnl wrote:
| Don't forget C# 1.0 which also shipped without generics. The
| people designing these langs were not inexperienced, far from
| it. Yet the mistake keeps being repeated every decade. I feel
| like the industry would be a lot further along if we paid more
| attention to these lessons from the past.
| tines wrote:
| Anders Hejlsberg, who designed C#, had previously designed
| Delphi, which has some support for generics (and I believe it
| had them before he left for Microsoft). I think the case may
| be that they're not making the same mistakes, but that
| they're just trying to ship software. Maybe though you would
| reply that generics are part of the minimum viable product of
| a programming language and it shouldn't ship without them. I
| can't say I disagree.
| layer8 wrote:
| When C# first came out it was in competition with Java,
| which at that point didn't have generics yet either. That
| was probably a relevant consideration for shipping the
| first version without generics.
| scoopertrooper wrote:
| Wow C# is much older than I thought.
| munificent wrote:
| _> Don 't forget C# 1.0 which also shipped without generics._
|
| That's true, but work to support them was already underway
| and when C# 2.0 shipped with generics, the bytecode and VM
| already supported it. That's why C# generics support
| specialization for non-reference types. Don Syme and company
| knew they wanted generics, but it takes time to design a
| system like that, so they shipped C# before that work was
| complete.
| KerrAvon wrote:
| Yes, considering the impact to the standard library, but
| generics are very hard to do well. The C++ language committee
| is still 30 years later dealing with the fallout from the
| underspecified initial template implementation. Java's
| implementation seems to get mixed reviews.
| layer8 wrote:
| Yes, it's not easy, but not designing them in from the
| beginning only imposes further restrictions on the eventual
| design. And the lesson has been that generics _will_ have to
| be designed in at some point for the language to stay
| relevant. Nowadays we at least have more existing languages
| -- and advances in type theory -- to learn from.
| [deleted]
| MrYellowP wrote:
| 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!
| SAI_Peregrinus wrote:
| If you don't have generics, you either check the data type at
| runtime (e.g. dynamic types, or dynamic dispatch in a
| statically-typed language) or you write different functions for
| every data type you want your function to handle.
| Jtsummers wrote:
| Generics are orthogonal to OO, they're about parameterizing
| your code with types (and sometimes values) rather than having
| to make many copies and tweaks for each possible
| specialization. Ada had generics in 1983, and only got OO in
| 1995.
| kaba0 wrote:
| 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.
| wvenable wrote:
| > 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.
| x-shadowban wrote:
| 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.
___________________________________________________________________
(page generated 2022-05-24 23:01 UTC)