Hacker News Reader

Comment by twoodfin | Hacker News Reader

Generalized multimethods are an inherently costly abstraction. This paper[1] provides a good survey of the state-of-the-art—at least as of 20 years ago—in the context of Dylan.

I'll have to re-read that section of Modern C++ to recall the runtime algorithm, but I'd be interested on any pointers to newer research or engineering on dispatch techniques.

It's too bad that (AFAIK) no 'mainstream' high performance language has a multiple dispatch abstraction that could motivate more work.

[1] http://www.eecs.berkeley.edu/~jrb/Projects/pd.pdf

View on HN

What about Julia? http://docs.julialang.org/en/release-0.4/manual/methods/

Julia does it right, but then also cheats. It uses high performance multi-methods, partially because it's a lisp and common lisp has been optimizing multi-methods for decades now. But also because Julia has a built in JIT with a very powerful type analyzer. Which means that while every function in Julia is a multi-method, you almost never pay the costs when writing high performance code.

The cheating comes from the run-time compilation features being leveraged to inspect "already compiled" code and dodge around the dispatch. However this causes problems in larger systems (Julia has some serious shortcomings when it comes to large projects, and they ban people who talk about it too much) because if you add a method to the multiple dispatch already compiled functions won't make use of it without recompiling them too, this is basically the expression problem being displayed in a dynamic language (because they choose speed over true dynamicism; they leverage the dynamic features for a different purpose and loose the feature typically gained). This is a very bad form of cheating because multi-methods are often seen as a solution to the expression problem, but Julia still has the problem even though they use multi-methods.

Try the following:

    # Library
    abstract bar

    ex(x) = println("dynamic")
    ex(x::bar) = println("bar")

    test(x::bar) = ex(x)

    type foo <: bar
      x :: Int
    end

    test(foo(5))

    # Now our code
    ex(x::foo) = println("foo")

    test(foo(5))

It should print `bar\nfoo` it doesn't.

I think this is slated to be fixed soon. Any reason why it can't be done?

https://github.com/JuliaLang/julia/issues/265

Look at the commits at the bottom.

It's probably doable, but also note how they say there will be a performance cost at runtime and it will be everywhere. Like I said, julia is cheating right now with the speed they are achieving while having multi-methods. It can be done, but they will loose their shiny performance numbers, or (for example) have to check to see if you need to recompile their entire standard library when you overload + while not crashing currently executing code. They are playing a shell game with the dynamic calls, and taking up large amounts of memory because of it, this will take up even more memory. And is another reason why Julia is not good for any large code base or doing anything but what the language was designed for.

There is no runtime cost to fixing this. You have to track dependencies between functions, which costs memory, and recompile functions when methods they depend on are changed, which costs compile time, but fixing this will not affect runtime performance.

The current behavior, although theoretically a problem, is not a big issue in practice. The reason is simple: unlike the example above, real-world programs tend to define a bunch of types and methods first and then the main program runs, using those types and methods.

Where it is actually a problem is in interactive development. At the REPL, people tend to redefine the same methods over and over, and it can be quite bothersome that those changes aren't always reflected. You can force an update by redefining the calling method as well, or you can just restart the REPL. Annoying, but not the end of the world.

I'll quote you as my response: "That would move the performance impact to runtime (and it would be everywhere)" and "You have to track dependencies between functions, which costs memory, and recompile functions when methods they depend on are changed, which costs compile time" and then quote myself "this will take up even more memory". Also I'd be curious to hear your thoughts on multi-threading.

Also real systems have many libraries. Which will each take turns in defining things. And some may run initialization code, causing certain things in their library to run. The fact of the matter is you don't have "real" multi-methods because of it, and it's a problem with making large systems.

I'm not saying that interleaving of execution and definition doesn't happen – it definitely does, that's how library loading works in dynamic languages. However, it is demonstrably not common to define methods for a type, call them, and then define methods that overwrite those methods.

But in a language with multi methods defining new extensions to the type hierarchy is defining methods that overwrite some other methods. If startup code for a library calls any methods which are later meant to be extended you are going to get weird unexpected behavior.

Lets see, there is a logging library with a custom string formatter, in another library I specialize the string formatter, and I log that the library started up with a value based on that abstract tag. Now as a user I specialize a concrete type for logging, but it doesn't work, why? That's a weird error, and also, the expression problem via multi-methods, well done you guys implemented multi-methods that don't solve one of the core purposes of multi-methods.

How much you wanna bet I can find startup code in many python libraries which calls code that is later specialized by users. Edge cases are where it's important.

Got it.

I'm wondering what this performance cost will be and if significant, can all that brainpower at MIT etc really not find a way to mitigate it?

This is a practical question for me because I'm considering Julia for a project and my personal data language.

This is the upcoming python alternative ecosystem, also with multi dispatch:

https://github.com/libdynd/libdynd https://github.com/numba/numba https://github.com/blaze/blaze

I mean scientific computing is what the language was designed for, use it if that's what you need.

Just don't expect to be using those shiny numbers for anything but scientific computing (and most specifically when involving large matrices). Their namespacing and modularity is terrible, writing a complex gui, non-trivial web server, 3d renderer, or any sort of real time system is right out. And they seem dead set against changing that (did I mention they ban people for making too much noise about it). But if you want to simulate something over a cluster it's a great choice.

I should probably note that I have a poor opinion of their community from my observations (they are hilariously salty), I may be a bit biased.

> Their namespacing and modularity is terrible, writing a complex gui, non-trivial web server, 3d renderer, or any sort of real time system is right out. And they seem dead set against changing that

There are many dozens of open issues discussing namespacing, interfaces, levels of type abstraction and extensibility, garbage collector improvements, i/o latency problems, task-switching performance, and more.

Prioritization of core effort in certain directions does not mean other issues are suppressed or even forgotten. Considerate proposals in other areas are welcome, and pull-requests implementing such proposals will be gratefully reviewed. They may not always be accepted -- immediately or sometimes ever. There is certainly some conservatism about adding features (such as interfaces), because features have costs and are near-impossible to remove once added. But other things just take time to get merged; for example, the generational GC took over a year, and there are other very large proposals that have been pending for longer than that because the implementation is lacking in some way or the implications are not fully worked-out to the point of consensus acceptance. That's ok, and IMHO healthy.

Except their consensus making prevents real needed features from seeing any progress, sure they have thousands of open issues on the topic, but when did any of them last move. Oh and arguing too strongly on controversial issues (hex stringification! oh no!) gets you banned (that was a hilarious read). So how is anything supposed to move when there is a split in the community?

You have an underinformed and incorrect understanding of what happened there. Leave it at that.

It looks like someone got banned for submitting a PR as a hypothetical solution which a core team member disagreed with, why would I ever contribute to a project like that.

Other people seem to agree on that point: http://danluu.com/julialang/

I'm not aware of any pull-requests implementing an incremental GC with pinning support, or any alternative module/namespacing scheme. Those would certainly be welcome.

As I said, the people actively working on the compiler have to prioritize because time and resources are finite. This is not the same as anyone being "dead set against changing", or a "ban people for making too much noise about it".

> when did any of them last move.

Here's a sampling of some improvements over the past 4 months.

- Debugging, everyone's priority by astronomic margins, has seen massive work and a recent preview-release (I've been using it since the announcement: rough edges, but very solid core): https://github.com/Keno/Gallium.jl/commits/master https://github.com/Keno/ASTInterpreter.jl/commits/master https://github.com/JuliaLang/julia/pull/15859 https://github.com/JuliaLang/julia/pull/15444

- Revamp of closures to make anonymous functions as fast as any other: https://github.com/JuliaLang/julia/pull/13412

- Significant compiler performance improvements: https://github.com/JuliaLang/julia/pull/15300 https://github.com/JuliaLang/julia/pull/14543 https://github.com/JuliaLang/julia/pull/15609

- Work towards static compilation (a number of PRs): http://juliacomputing.com/blog/2016/02/09/static-julia.html

- Multithreading improvements: https://github.com/JuliaLang/julia/pull/15917 https://github.com/JuliaLang/julia/pull/15106

- Someone else pointed you to recent commits toward fixing the recompilation issue.

Can you explain why you couldn't write a 3D renderer or complex gui in Julia? As someone who does exactly that it's a bit hard to follow your reasoning...

Well, real-time 3d rendering anyway, thanks to the garbage collector and having very little control over it. How complex of a GUI are we talking here? Do you split it into many namespaces? Have long load times when not on a powerful dev machine? Ever tried to deploy said GUI? Do the right thing when exceptions in your program happen, or does it just crash the GUI or spit you out to the repl? Because I'm betting your GUI is not meant to be used by anyone but a couple of people with familiarity with the system, which is fine, but not generally what a GUI is made for.

deployment + load times: obviously things aren't perfect, Julia is at version 0.4, after all ;) There are a lot of low hanging fruits for compile time and deployment, so I'm sure that the situation will look a lot different in a year or two.

I'm not sure why Julia itself should make it difficult to "do the right thing" when exceptions occur...

Real-time 3D rendering is a big area. Will we have virtual reality with ultra low latency in the next year? Definitely not! Can we have 3D CAD/scientific visualizations which hardly stutters? Definitely! Our library is already very smooth and we didn't even start optimizing yet. That's something that seems to be almost impossible in e.g Python (without just calling C for everything).

So while most of these arguments are currently spot on, I do think that there is nothing fundamentally wrong with Julia. And while the maturity is not there yet, you can already be very productive with Julia and build for the future.

"I'm not sure why Julia itself should make it difficult to "do the right thing" when exceptions occur..."

Untyped, sometimes incorrect, exceptions, https://github.com/JuliaLang/julia/issues/12485 and related.

Yeah and there is already an improvement to that: https://github.com/JuliaLang/julia/pull/12541. Well, anyways, I think you can easily find a lot of unsatisfactory constructs in any language, especially in young ones ;) If they outweigh the advantages is debatable. So far I've been finding satisfactory workarounds for the most daring issues, so for me the conclusion is indeed very positive.

Is there any dynamic language suitable for real time 3d viz?

Reference counted ones, by carefully controlling when the reference count for objects are released you can make sure that the rendering thread never has to do any of the expensive ones, and instead all (non-trivial) reference releases are shunted off into a different thread for deallocation. In the general case you don't care, and in the specific case you have a fine enough control you can get around the problem of unknown gc-pauses. It's slower - it is a dynamic language afterall - but it's consistent and real-time is more about being consistent.

gotcha

Thanks for sharing your thoughts.

I want to keep my general code and scientific code in the same language.

So python it is.

> Julia has some serious shortcomings when it comes to large projects, and they ban people who talk about it too much

Only one person has ever been banned on GitHub and it was not for talking about any shortcomings. That person is still allowed to and regularly does post on Julia mailing lists – no one has ever been banned from mailing lists.

Shrug I've never seen the mailing lists for Julia, I just recently started reading the github every now and then because it is an interesting language, and I like seeing the development of it. But ~~your community is~~ you are one of the most hilariously salty one's I've ever watched. And sorry but it does look like you banned him for being pushy about the problems making modular software, and doing real development with the language. Which I note you don't dispute.

The main mailing list is here, people can judge for themselves:

https://groups.google.com/forum/#!forum/julia-users

Here's a recent (and typical) example of a lengthy series of technical and sometimes pointedly-critical questions:

https://groups.google.com/forum/#!searchin/julia-users/%22ve...

HN is not the right forum for this, but that's definitely not why he was banned.

Stroustrup's paper (mentioned in the article) about implementing this in C++ is pretty comprehensive and deals with performance as well.

Reply on news.ycombinator.com