Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

When Big O Fools You

jackmott.github.io

Post reply on HN
Print view View original

121–130 of 134 posts

Re: When Big O Fools You

#121

Post by Koromix »

qwertyuiop924 wrote: post #108
Koromix wrote: post #89

Earlier quoted context omitted.

> That doesn't sound like a cache miss. Knowing Android, A cache miss is probably the least of your worries. My example was meant to illustrate the user input problem. From what I know about Android, the absymal performance is very much a case of "death from a thousand cuts". > It's the same argument as always: perf vs. development speed. You can be in the C and FP loop, or the Lisp and JS loop. The fast(er) language…

>But here's the thing: we could have both at the same time. I don't buy this dichotomy. That's actually not true: OO, dynamism, late binding, and a lot of the other things that HLLs have to offer require a lot of pointer chasing and non-consecutive datastructures. I'm mostly a Schemer, and Scheme and Lisp have had decades of research put into making them compile and run fast. Most dynamic languages aren't so lucky. B…

> OO, dynamism, late binding

None of these are required for ease of development. At least the first two often result in precisely the opposite.

HLLs are not required to focus on slow abstractions. For example, homogeneous arrays of tagged unions can replace inheritance most of the time. And they avoid breaking your code in 10 files and 20 classes (though for some reason this metric is seen as a good thing way too often).

Re: When Big O Fools You

#122

Post by johncolanduoni »

Retra wrote: post #115
johncolanduoni wrote: post #106

Earlier quoted context omitted.

This isn't true at all. What's the cost in developer resources, cpu, or memory of making a complex number class in C++ a template over floats and doubles? How about the cost of using Rust's generics to make a parser that can parse from any linear source of bytes (e.g. both files and in memory byte arrays)? There's plenty of abstractions which don't actually cost anything, and there's room for even more.

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 is.

> Dynamic library bloat.

Your alternatives are A. duplicate the classes yourself B. let the compiler duplicate them. Where's the bloat? C++ requires you to explicitly instantiate templates if you want them in a library, and usually they're just left to the header. The others I listed won't generate anything unless you actually use a particular instantiation.

> developer time is spent dealing with all of this

It's pretty hard to argue that more developer time is wasted by the compiler writer than that of the time saved for developers who use the language for such a broadly used feature.

> Abstractions leak because they are models, and thus are necessarily different from the concrete things that they model.

What concrete thing do generics model? Tediously copy-pasted code? These will only be different if you mess up when you do the copy-pasting.

> Generic programming is an abstraction that pretends you aren't working on low-level un-typed system.

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.

"All abstractions leak" is a nice platitude, but handwaving about "models" and "concreteness" doesn't prove anything.

Re: When Big O Fools You

#123

Post by stcredzero »

_benedict wrote: post #97
stcredzero wrote: post #44

Earlier quoted context omitted.

The programming field isn't lacking in typical programmers with hypotheses. What it's lacking are typical programmers who are checking their hypotheses.

If you take the word hypothesis at its meanest, and ignore everything else I said, sure. But a hypothesis that is grounded in an absence of analysis or understanding of the situation, or an appreciation of the existing body of literature related to a topic, or any other informing principle, is of limited value. i.e., it's not about checking your hypothesis, it's about checking the method by which you formed your hypo…

Many would rate Aristotle as a 1st rate thinker. Too bad he didn't check his hypotheses more.

Re: When Big O Fools You

#124

Post by qwertyuiop924 »

Koromix wrote: post #121
qwertyuiop924 wrote: post #108

Earlier quoted context omitted.

>But here's the thing: we could have both at the same time. I don't buy this dichotomy. That's actually not true: OO, dynamism, late binding, and a lot of the other things that HLLs have to offer require a lot of pointer chasing and non-consecutive datastructures. I'm mostly a Schemer, and Scheme and Lisp have had decades of research put into making them compile and run fast. Most dynamic languages aren't so lucky. B…

> OO, dynamism, late binding None of these are required for ease of development. At least the first two often result in precisely the opposite. HLLs are not required to focus on slow abstractions. For example, homogeneous arrays of tagged unions can replace inheritance most of the time. And they avoid breaking your code in 10 files and 20 classes (though for some reason this metric is seen as a good thing way too oft…

OO, perhaps, but without dynamism and late binding, metaprogramming is difficult, as is any number of techniques. Like, for instance, class generation, and extending methods.

And while I don't set much store by inheritance, it set considerably more store by duck-typing and polymorphism.

>None of these are required for ease of development. At least the first two often result in precisely the opposite.

So are you talking about Java-style OO? Because I was talking about Smalltalk OO, which is pretty different.

Required, no, but they're tools, and they come in handy. Certainly make development a lot more comfortable.

And some of the time, they make delvelopment a lot easier.

Re: When Big O Fools You

#125

Post by _benedict »

vonmoltke wrote: post #113
_benedict wrote: post #96

Earlier quoted context omitted.

I deleted from my comment an explicit calling out of this feedback loop, as it was implied, I thought, by the statement that the measurement and testing were both important, but of limited value by themselves. However I disagree that measurements have any meaning unless they are conducted as experiments, or potentially as exploratory work looking for an experiment to conduct. Even such exploratory work needs to be dr…

> However I disagree that measurements have any meaning unless they are conducted as experiments, or potentially as exploratory work looking for an experiment to conduct. Even such exploratory work needs to be driven by at least the loosest of hypotheses, since measuring everything is infeasible. So this is just as much an experiment, just one you don't have a high expectation of predicting the outcome of. > Either w…

But now you're ignoring the rest of my initial post, which stated the use of understanding and analysis of the situation to form your hypothesis.

Honestly I think we probably agree and (we, both) are just having a semantic circle-jerk at this point though.

Re: When Big O Fools You

#126

Post by Koromix »

qwertyuiop924 wrote: post #124
Koromix wrote: post #121

Earlier quoted context omitted.

> OO, dynamism, late binding None of these are required for ease of development. At least the first two often result in precisely the opposite. HLLs are not required to focus on slow abstractions. For example, homogeneous arrays of tagged unions can replace inheritance most of the time. And they avoid breaking your code in 10 files and 20 classes (though for some reason this metric is seen as a good thing way too oft…

OO, perhaps, but without dynamism and late binding, metaprogramming is difficult, as is any number of techniques. Like, for instance, class generation, and extending methods. And while I don't set much store by inheritance, it set considerably more store by duck-typing and polymorphism. >None of these are required for ease of development. At least the first two often result in precisely the opposite. So are you talki…

> Like, for instance, class generation, and extending methods.

This is precisely the kind of thing that leads to unmaintainable "magic" code, even though it can still be useful but with extreme moderation. So I don't see the point of making that a core feature of any language.

If you have any example to the contrary, I'd love a link to a good open-source project that uses these things extensively.

Re: When Big O Fools You

#127

Post by qwertyuiop924 »

Koromix wrote: post #126
qwertyuiop924 wrote: post #124

Earlier quoted context omitted.

OO, perhaps, but without dynamism and late binding, metaprogramming is difficult, as is any number of techniques. Like, for instance, class generation, and extending methods. And while I don't set much store by inheritance, it set considerably more store by duck-typing and polymorphism. >None of these are required for ease of development. At least the first two often result in precisely the opposite. So are you talki…

> Like, for instance, class generation, and extending methods. This is precisely the kind of thing that leads to unmaintainable "magic" code, even though it can still be useful but with extreme moderation. So I don't see the point of making that a core feature of any language. If you have any example to the contrary, I'd love a link to a good open-source project that uses these things extensively.

RSpec? A lot of ruby uses metaprogramming in some respect.

As for not seeing the point of making it a feature of your language, how about Lisp? And I'm not just talking macros. Lambdas, late binding, and in Scheme, the ability to rebind anything lead to a lot of cool tricks and capabilities.

And late binding is extrordinarily important.!

Re: When Big O Fools You

#128

Post by Koromix »

qwertyuiop924 wrote: post #127
Koromix wrote: post #126

Earlier quoted context omitted.

> Like, for instance, class generation, and extending methods. This is precisely the kind of thing that leads to unmaintainable "magic" code, even though it can still be useful but with extreme moderation. So I don't see the point of making that a core feature of any language. If you have any example to the contrary, I'd love a link to a good open-source project that uses these things extensively.

RSpec? A lot of ruby uses metaprogramming in some respect. As for not seeing the point of making it a feature of your language, how about Lisp? And I'm not just talking macros. Lambdas, late binding, and in Scheme, the ability to rebind anything lead to a lot of cool tricks and capabilities. And late binding is extrordinarily important.!

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.

Re: When Big O Fools You

#129

Post by dottrap »

Danieru wrote: post #110
fixerfrasse wrote: post #78

Earlier quoted context omitted.

Afaik, if you read in reverse, then you will miss cache optimization since it only works forward.

Intel cache prediction will detect both forward, backward, and some odd movement patterns. It has not been only forward prediction for a very long time.

Do you know how the popular ARM based chips fare in comparison?

Re: When Big O Fools You

#130

Post by qwertyuiop924 »

Koromix wrote: post #128
qwertyuiop924 wrote: post #127

Earlier quoted context omitted.

RSpec? A lot of ruby uses metaprogramming in some respect. As for not seeing the point of making it a feature of your language, how about Lisp? And I'm not just talking macros. Lambdas, late binding, and in Scheme, the ability to rebind anything lead to a lot of cool tricks and capabilities. And late binding is extrordinarily important.!

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 metaprogramming principles.

tclOO, [incr tcl], and other OO TCL systems are usually implemented in regular TCL.

Give or take, any large Lisp or Smalltalk codebase takes advantage of dynamic typing, late binding, and some form of metaprogramming.

However, you've made it clear that you hate Ruby, Dynamic Typing, and other such things, as given as much of metaprogramming requires this sort of flexibility, I very much doubt anything I say will convince you that dynamic languages are in any way useful.

Post reply on HN