We call these "system images" and you can generate them with PackageCompiler [0]. Unfortunately, it's still a little cumbersome to create them, but this is something that we're improving from release to release. One possible future is where an environment can be "baked", such that when you start Julia pointing to that environment (via `--project`) it loads all the packages more or less instantaneously.
The downside is that generating system images can be quite slow, so we're still working on ways to generate them incrementally. In any case, if you're inspired to work on this kind of stuff, it's definitely something the entire community is interested in!
Yeah, we've managed to get Julia itself running pretty well on the M1, there are still a few outstanding issues such as backtraces not being as high-quality as on other platforms. You can see the overall tracking issue [0] for a more granular status on the platform support.
For the package ecosystem as a whole, we will be slowly increasing the number of third-party packages that are built for aarch64-darwin, but this is a major undertaking, so I don't expect it to be truly "finished" for 3-6 months. This is due to both technical issues (packages may not build cleanly on aarch64-darwin and may need some patching/updating especially since some of our compilers like gfortran are prerelease testing builds, building for aarch64-darwin means that the packages must be marked as compatible with Julia 1.6+ only--due to a limitation in Julia 1.5-, etc...) as well as practical (Our packaging team is primarily volunteers and they only have so much bandwidth to help fix compilation issues).
They are talking about total operations, but since big O notation ignores constant factors, and they explicitly ignore the addition steps (because for large n multiplication dominates) it is, in effect, only looking at the multiplications.
To answer the GP, the minimum amount of work necessary is to write a number for each element in the array, which scales by n^2 since there are n^2 elements. It is of course only possible to beat this if you can make assumptions like “the diagonal of my matrix is nonzero and everything else is zero”, but that’s not general matrix multiplication anymore, that’s a specialized sparse matrix routine. For a dense, “normal” matrix, O(n^2) is the absolute best we could hope for.
We're saying approximately the same thing, though I'd argue that your phrasing is slightly more confusing to people that aren't super familiar with Big O notation (and therefore don't exactly understand what is meant by "ignores constant factors" and similar).
Reads from the original two matrices and writes to the final matrix aren't at all the crux of the problem, so I don't think it makes sense to focus on either of those things in your explanation. The goal of the problem is to reduce the number of multiplications which are required to find the values that you then write (of which there will always be n^2 writes). There will also be 2n^2 reads, but likewise that isn't relevant because it's not what you're trying to optimize.
The relevant idea here is that the naive method of multiplying a matrix involves n multiplications for every row-column pair, for a total time complexity of n^3 (n rows, n cols, n multiplications). The goal here is to bring down that third number, from n down to something >= 1, with the holy grail obviously being 1 itself.
It's not at all obvious to me why the number of multiplications must be at least n². Can you prove that? (To be clear, n² multiplications is most certainly the lower bound, but I can't come up with a good argument as to why.)
This is why the trivial "you must read n² entries from each input matrix and write n² entries in the end" is helpful: It's an extremely obvious lower bound on the asymptotic complexity. Sure, it's not what we're trying to reduce (and getting < n² multiplications would be a ridiculous result), but anyone can see that it's true.
If matrix A has a single nonzero column (ai) in the first column and B has a single nonzero row (bj) in the first row, then A * B computes all pairwise products ai * bj.
To be honest I’m not sure whether that really proves it. Does computing a single multiplication require a multiplication?
By definition, a matrix multiplication takes rows and multiplies them by columns. For a pair of square matrices, where there are n rows in A and n columns in B, you (by definition) need to multiply them by each other at least once, otherwise it's not matrix multiplication, it's matrix... something else.
> By definition, a matrix multiplication takes rows and multiplies them by columns.
> you (by definition) need to multiply them by each other at least once
Why does multiplying a row with a column require at least one multiplication? "By definition" it takes n multiplications (!), but in the context of matrix multiplication we can do it with less - possibly with O(1) multiplications. And it seems neither you nor me can come up with a good argument why it can't take less, despite discussing it for a while.
Which is why "you need to write n² entries" is used as an argument for the O(n²) bound, even if it has nothing to do with the number of multiplications.
You pay a price for the super-small frame sizes; much worse compression ratios. Frame sizes smaller than 10ms disable the LPC and hybrid coding modes, which are quite advantageous. [0]
In my experiments with transmitting realtime audio signals using Opus, 10ms frame sizes are acceptable for 1-way synchronicity (e.g. if you want the user to perform an action and hear the result as simultaneous with the action) but it's definitely the upper bound. From what I remember my signal processing professor say, the threshold to try and hit is 7ms total latency for truly undetectable processing, but I can't find a reference for that, so take it with a grain of salt.
Robert H. Jack, Tony Stockman, and Andrew McPherson. 2016. Effect of latency on performer interaction and subjective quality assessment of a digital musical instrument. In Proceedings of the Audio Mostly 2016 (AM '16). Association for Computing Machinery, New York, NY, USA, 116–123. DOI: https://doi.org/10.1145/2986416.2986428
Here in Seattle, in the absence of traffic forcing slower speeds, most people are going ~10mph over the speed limit. On the freeway, although the speed limit is 60mph most people will be going about 70mph. If you use Tesla's autopilot it will match the speed of the car in front of you, up to the maximum specified by the "speed limit". So I usually set the speed limit to something like 75mph so that the car follows the flow of the traffic around it, instead of forcing other drivers to swerve around me because I am going 10mph slower than everyone else.
The abstractions that are built up within that codebase feel very clean, like they get out of your way so that you can be productive, without drowning you in syntax.
Julia's SIMD programming model is still very much a work in progress; I think we have a way to go in providing the kind of flexibility and control that languages such as ISPC, Halide, TVM, etc... provide.
That being said, packages such as SIMD.jl [0], and LoopVectorization.jl [1] are making fantastic progress, to the point that LoopVectorization forms the basis of a legitimate BLAS contender, in pure Julia [2]. It's not totally there yet, but it's close enough that real work is being done in LV at OpenBLAS-like speeds.
As an aside, I find it incredible that these kinds of extensions can be built in packages thanks to the fact that Julia's compiler is extensible enough to allow for direct manipulation of the LLVM intrinsics being emitted by user code.
ISPC can be really good at SIMD-ing complicated control flow (ray tracers being the archetypal example).
I'm interested in eventually working on something like that for Julia.
In the mean time, it should be possible to deliberately write code to be compatible with something like SIMD.jl.
I think I'd work on a project of trying to get that working via multiple dispatch with at least a moderately complex project, and let those experiences inform the kind of transforms an automatic compiler would need to both work and get good performance.
I didn't take it as such; there are legitimate shortcomings to any tool, I just wanted to provide pointers to other readers that the devs are aware of it, and that there is ongoing development to address it. :)
> Come on, jeez.. Julia’s compiler is a Lisp-based LLVM driver: of course it can do these things.
As someone who, before Julia, was firmly entrenched in C/C++/Python land, I suppose I am discovering many of these "obvious" things for the first time. :)
No need to be shy! Quality work is quality work, no matter when it is submitted, and earlier is usually better! If DO is going to give out free t-shirts, there's no reason to purposefully deprive yourself of them just because someone wrote a blog post.
The Julia Language [0] gets some spammy issues/pull requests as well (not only during October) and while we have the benefit of dozens of maintainers such that it's bearable, I definitely sympathize with the issues OP is dealing with. Opt-in could be a good idea, although as usual, the issue is scaling and verification.
While it's true that all code is typed (e.g. the compiler knows what types to expect at different points throughout the program), it's completely possible to have essentially "worthless" types computed. E.g. if I have the following:
foo(x::Int) = x + 1
foo(x::Float64) = x + 2
foo(x::String) = "$(x) $(x)"
function eval_user_input()
user_input = readline(stdin)
user_obj = eval(Meta.parse(user_input))
return foo(user_obj)
end
Then clearly there is no way the compiler can know what the type of `user_obj` is, however it will do its best to infer the entire function. We can use `@code_warntype` to quickly and easily find places where Julia's type inference gives a suboptimal result (which is often a source of performance issues, since there will be runtime overhead in those cases).
You can see that `user_obj` is annotated as type `Any`, and that invoking `foo()` is said to itself return a type of `Union{Float64, Int64, String}`, which is to say, it has no idea which `foo` it's going to call ahead of time. I will note that in the REPL, all the suboptimal stuff is highlighted in red, making this a very nice debugging tool for immediately finding poorly-inferred sections of code. If we ask the compiler to run this code through its optimization passes as well by passing the `optimize=true` flag to `@code_warntype`, we can even see how the compiler tries to inline `foo` by turning the call to `foo()` into a series of `isa()` conditionals, checking the type of the return from `eval()`. I'm pasting the relevant section here, for the full example you can see the screenshot linked below, showcasing the red highlighting as well:
The downside is that generating system images can be quite slow, so we're still working on ways to generate them incrementally. In any case, if you're inspired to work on this kind of stuff, it's definitely something the entire community is interested in!
[0] https://github.com/JuliaLang/PackageCompiler.jl