When Big O Fools You • Hacker News Board

Re: When Big O Fools You

#131

Post by Koromix » Wed, Aug 24, 2016, 4:19 PM UTC

qwertyuiop924 wrote: post #130

Koromix wrote: post #128

Earlier quoted context omitted.

I don't consider the Ruby ecosystem to be a good example of much. Idiomatic Ruby code is much slower and usually not more maintainable than C++. Actually, it may even be worse thanks to dynamic typing, which makes refactoring much more painful than it already is in large code bases. Well I guess it's good at making CRUD web sites. Hardly rocket science.

Okay then: Lisp. Tinyclos is a fairly sophisticated implementation of OO and the MOP, written in Scheme. Its descendants, COOPS, GOOPS, and others, are in most schemes today. Many of them are written in their respective dialect of scheme, with little or no specific compiler support. SXML allows for writing XML in native scheme syntax. The anaphoric macros (aif, acond, etc.) are all, well, macros, and thus use metapro…

I don't hate them. I've used python more than once, and will continue to do so. And I think it's great teaching material. It's a good scripting language. But I think its drawbacks far outweigh its advantages for large projects.

All your examples are programming gimmicks, and I've yet to see stuff that solves actual hard problems. I'm not interested in programming for programming's sake. I want to use it to make my computer do useful stuff.

Re: When Big O Fools You

#132

Post by qwertyuiop924 » Wed, Aug 24, 2016, 5:23 PM UTC

Koromix wrote: post #131

qwertyuiop924 wrote: post #130

Earlier quoted context omitted.

Okay then: Lisp. Tinyclos is a fairly sophisticated implementation of OO and the MOP, written in Scheme. Its descendants, COOPS, GOOPS, and others, are in most schemes today. Many of them are written in their respective dialect of scheme, with little or no specific compiler support. SXML allows for writing XML in native scheme syntax. The anaphoric macros (aif, acond, etc.) are all, well, macros, and thus use metapro…

I don't hate them. I've used python more than once, and will continue to do so. And I think it's great teaching material. It's a good scripting language. But I think its drawbacks far outweigh its advantages for large projects. All your examples are programming gimmicks, and I've yet to see stuff that solves actual hard problems. I'm not interested in programming for programming's sake. I want to use it to make my co…

Gimmicks? Some of them, yes, but CLOS and its descendants are used in Real applications, as are the TCL OO systems. But if you want Real World, I'll give you real world.

Maxima is a descendant of the original MACSYMA, developed at MIT. It is still a usable and viable system, even if it has ageda bit.

Emacs is a popular programmer's text editor written in C and a dialect of lisp.

Both of the above programs are large, useful, and written in an HLL - one particularly amenable to pointer chasing, I might add - and they make use of the variety of abstractions which that HLL provides.

If those aren't modern enough for you, check out some Clojure applications.

Re: When Big O Fools You

#133

Post by Retra » Thu, Aug 25, 2016, 2:43 AM UTC

johncolanduoni wrote: post #122

Retra wrote: post #115

Earlier quoted context omitted.

What's the cost in making a template more generic? Greater compile time. Need for compiler that can handle generics. Greater number of functions in binaries, and thus more unique places for bugs to occur. Dynamic library bloat. Harder to understand code. Quirky edge cases. Harder to learn languages. Harder to parse languages. And of course, developer time is spent dealing with all of this. Abstractions leak because t…

> Greater compile time. Not really with newer generics implementations (.NET, Rust, etc.). I don't think anyone thinks C++ templates are ideal, and the others show this at least a non-essential cost. > Greater number of functions in binaries, and thus more unique places for bugs to occur. Less human written code, so this reduces the surface area to the compiler; which is an "issue" no matter how low level your code i…

You seem to be misunderstanding the generality at which I'm speaking. Take this:

>It's pretty hard to argue that more developer time is wasted

That's NOT what I'm arguing. I'm saying that it takes a different amount of time. Hence the concept of "trade-offs", AKA "cost."

With that said...

>Your alternatives are A. duplicate the classes yourself B. let the compiler duplicate them. Where's the bloat?

C. Monomorphise at runtime.

>Less human written code, so this reduces the surface area to the compiler; which is an "issue" no matter how low level your code is.

Yes, but it's a different issue. Again, there are trade-offs.

>What concrete thing do generics model? Tediously copy-pasted code?

No. They model the behavior of the algorithm as it physically exists in a machine.

>What? It's an abstraction over an already typed system that obviates the need to duplicate code, which after the generics are unwound produces the same code you would have had anyway. You're just as far or close to the low-level un-typed system as you were before.

Generics are part of your language. They do not abstract over the language. They abstract over the behavior of your program. It's just a feature of the language that does so with greater generality that the rest of the language.

And the code you "would have written anyway" is machine code. Which you are abstracting over. Generics allow you to pretend your algorithm doesn't need a fixed machine representation. The fact that you can produce two different machine representations for the same template code is an example of what I'm talking about, not a counter example. The abstraction leaks. You write one algorithm, and it has to be compiled into two different representations. That's the cost of the abstraction. You get increased generality at the cost of memory and time.

Re: When Big O Fools You

#134

Post by johncolanduoni » Thu, Aug 25, 2016, 7:25 AM UTC

Retra wrote: post #133

johncolanduoni wrote: post #122

Earlier quoted context omitted.

> Greater compile time. Not really with newer generics implementations (.NET, Rust, etc.). I don't think anyone thinks C++ templates are ideal, and the others show this at least a non-essential cost. > Greater number of functions in binaries, and thus more unique places for bugs to occur. Less human written code, so this reduces the surface area to the compiler; which is an "issue" no matter how low level your code i…

You seem to be misunderstanding the generality at which I'm speaking. Take this: >It's pretty hard to argue that more developer time is wasted That's NOT what I'm arguing. I'm saying that it takes a different amount of time. Hence the concept of "trade-offs", AKA "cost." With that said... >Your alternatives are A. duplicate the classes yourself B. let the compiler duplicate them. Where's the bloat? C. Monomorphise at…

> Generics are part of your language. They do not abstract over the language.

Most generics systems allow the code to be unfolded into generic free code; this is how templates are usually compiled in C++. So in a material sense the compiler treats templates as syntactic sugar added over C++ without templates (which is a valid language, which the compiler uses internally).

> C. Monomorphise at runtime.

A lot of generics (like my complex number example) can't be monomorphized at runtime since floats and doubles don't have dynamic dispatch in these languages. Not to mention the loss of type safety even if you implemented it this way. So that is not equivalent.

> And the code you "would have written anyway" is machine code.

That's not analyzing the cost of generics, that's analyzing the cost of the whole language, and then putting it on generics. If that's fair, why wouldn't we add the cost of designing and operating computers instead of doing it on paper? There's nothing special about machine code here.

> The abstraction leaks. You write one algorithm, and it has to be compiled into two different representations. That's the cost of the abstraction.

If (as in my example before) you need complex numbers with floating point numbers, and complex numbers with doubles, the compilation will likely be faster because the compiler doesn't need to take two parallel implementations through the whole parsing process, and can instead generate the necessary ASG itself. If you use on only one, then maybe there is a detectable differential cost.

Also, how is that even a leak? That's the abstraction working absolutely perfectly and giving you exactly what you intended.