[HN Gopher] Type Stability in Julia: Avoiding Performance Pathol... ___________________________________________________________________ Type Stability in Julia: Avoiding Performance Pathologies in JIT Compilation Author : leephillips Score : 55 points Date : 2021-12-08 19:57 UTC (3 hours ago) (HTM) web link (arxiv.org) (TXT) w3m dump (arxiv.org) | ulysses4ever wrote: | Author here. AMA! | dklend122 wrote: | Hi, cool paper! semi related questions: | | What do you think of JET.jl? | | Tension between Method ambiguities and desire for traits or | multiple inheritance is something discussed in the community. | Has your group given any thought to this? | | Thanks ! | ulysses4ever wrote: | Hey! we're tracking JET.jl and think that it's great already | and may become even better. We hope to base some of our | future stuf off it. Some of us (not me) actually work on a | trait design. Multiple inheritance -- not so much: we think | it would preclude some important optimizations and that way | defeat the whole purpose of Julia (performance + dynamism). | amkkma wrote: | Cool! Any repos or anywhere I can track the trait stuff? | Would they be interested in interfacing with some people in | the community who have worked on some trait packages/ have | experience and thoughts about adhoc method based traits in | practice? | Sukera wrote: | Hi, thank you! The paper mentions that the dynamic analysis | code is written in julia and could be used by package | developers to study instabilities in their code, but I couldn't | find a link to the code in the references. Did I just miss it | or is it contained in the zip containing the visualization | data? | | -- | | EDIT: Nevermind, found it in the zip! | ulysses4ever wrote: | I think the link's supposed to be in the text but the repo is | here: https://github.com/prl-julia/julia-type-stability | There's a PDF there explaining how to get started with it and | repro the graphs but it shouldn't be too hard to utilize it | for the purpose you mention. We never got around to writing | that kind of docs (for package developers) properly | unfortunately. Feel free to open issues against the repo if | you have troubles using it! | Sukera wrote: | Ah, that link doeesn't seem to be in the paper (at least my | searching for `github` didn't turn up anything), thank you! | I did however find the same code as part of the | visualization, so I got what I was looking for. | ulysses4ever wrote: | That's my bad then. I think I might have thought Zenodo | link would be enough. But now I think it's a bad idea. | Probably will add the GH link in an update. | StefanKarpinski wrote: | I'm still working through the paper--reading your group's Julia | papers is always a great treat--thank you for this one and all | of them. Looking at the definition of "type groundedness" it | seemed to me that perhaps the definition should require that | "every _expression's_ type depends only on the argument types " | rather than only variables. I haven't gotten to the proof | parts, but this was just a thing that struck me early on. | ulysses4ever wrote: | Your intuition is right but _every_ expression is bound by a | variable in this representation. | StefanKarpinski wrote: | Ah, ok. I hadn't gotten to that part yet. Would it make | sense to change the general definition to "expressions" | since that would be the correct definition for Julia code | as well as the Jules IR format? | ulysses4ever wrote: | This may require more thinking on our end but the way we | design Jules is the usual SSA form. The idea being it's | easier to reason about it (and prove things) when every | expression has a name. It's a bit of cheating of course | but makes our life easier. We don't discuss how surface | Julia (or subset of it), which is more expression- | oriented, can be translated to Jules, because we have | only so many pages, and also it's not all that | interesting, I think. | celeritascelery wrote: | I am not familiar with Julia, but it seems like the common | feature of "automatic big num conversion" would work against | optimization like this correct? Because the output type no longer | depends on the input types, but also there values. | freemint wrote: | You are correct that "automatic big num conversion" works much | against optimization. Int{8,16,32,64,128} in Julia also | overflow silently. If you want other behaviour you can write | your own custom behavior and "overload" +,* for your type. | SafeIntegers throws an exception on overflow. Switching to | BigInt would also be possible to implement but i am not aware | of any package that does that or if it would give performance | benefit over just using BitInt to begin with. | Sukera wrote: | Another alternative is to use the Base.Checked.* family of | functions, though they have different names than (+) like | checked_add and thus have to be explicitly used. | freemint wrote: | Which is what SafeInteger does internally. Checked is kinda | obscure but i added a doc string to it which was merged | with the main branch today. | Sukera wrote: | If you're thinking about how in e.g. python, integer addition | never overflows and is always a big integer, then yes. If | "small"/machine integers and big integers are seperated each | have a distinct type, promotion on overflow would introduce a | type instability on every addition (not only the overflowing | one!). This is precisely because the type would depend on the | result of the addition, not only the input types (which may | both be machine integer types). | | A "solution" to this conundrum is to have big integers by | default, which sadly isn't feasible for performance reasons - | you can't then take advantage of hardware, because every | operation necessarily has to do more work than would be | required for machine integers. | | -- | | To add on to this, when encountering overflow (which doesn't | happen often in the first place), it's usually sufficient to go | for 128 bit integers first instead of jumping directly to big | integers. They're still quite a bit faster and offer a much | larger space to work with. | StefanKarpinski wrote: | This is one of the reasons that Julia doesn't do automatic big | num conversion, instead using native machine two's complement | modular arithmetic for integers. It would be a good | optimization to use an immediate representation for small | bignums, however. See this FAQ entry | https://docs.julialang.org/en/v1/manual/faq/#faq-integer-ari... | on the subject. | chrisseaton wrote: | It would only depend on the value if the operation had actually | overflowed in the past, in which case performance is already | going to be poor. | krastanov wrote: | There is an interesting story here that I wish was told in more | details somewhere on the internet (currently I just have some | partial guesses from listening to JuliaCon talks). It seems some | of these (awesome) properties arose very organically after | experimentation, not by having a committee of theorists define | the properties the language should have. This has led to a couple | of minor inconsistencies to be ironed out, however computer | scientists (like the authors of this paper) then decided to study | and formalize Julia and uncovered gems like this (I guess they | are gems particularly if you care about formal treatments). | | I am certain I am somewhat wrong in this description, but I would | love to see a writeup of the whole story and how both sides (the | devs and the scientists) lived through it. | ulysses4ever wrote: | You're quite right about the organic nature. The story of how | we get together could be better told by our prof, Jan Vitek, I | guess. But in a nutshell, one of his older students (Ben, also | an author of the paper) was once on a plane with some other | student, Jean, from MIT, where Julia was developed, and Ben got | interested and told Jan... Then there were occasional meetings | with Julia devs (Jeff Bezanson in particular) that turned out | to be super nice and inviting people. I should add, we're all | from Northeastern University in Boston, and that's close to | MIT... All in all, we decided PL academia should learn about | this "organic gem". ___________________________________________________________________ (page generated 2021-12-08 23:00 UTC)