4 ms·
Oh, array striding. This is a classic bikeshedding issue. When Go and Rust were first being designed, I brought up support for multidimensional arrays. For bot
by Animats 3y ago
Oh, array striding.
This is a classic bikeshedding issue. When Go and Rust were first being designed, I brought up support for multidimensional arrays. For both cases, that became lost in discussions over what features arrays should have. Subarrays, like slices but multidimensional? That's the main use case for striding. Flattening in more than one dimension? And some people want sparse arrays. Stuff like that. So the problem gets pushed off onto collection classes, there's no standard, and everybody using such arrays spends time doing format conversion. This is why FORTRAN and Matlab still have strong positions in number-crunching.
- lifthrasiir 3y agoBut format conversion is inevitable because C and FORTRAN has a different axis ordering anyway, isn't it?
- blt 3y agoNot really, you can always change the indexing to account for it. For example, the GEMM matrix multiplication subroutines from BLAS can transpose their arguments [1]. So if you have A (m x n) and B (n x p) stored row-major, but you want to use a column-major BLAS to compute A*B, you can instead tell BLAS that A is n x m, B is p x n, and you want to compute A' * B'. As the article mentions, NumPy can handle both and do all the bookkeeping. So can Eigen in C++. [1] https://www.math.utah.edu/software/lapack/lapack-blas/dgemm.html https://www.math.utah.edu/software/lapack/lapack-blas/dgemm....
- lifthrasiir 3y agoThat's conceptually still a format conversion, though the actual conversion might not happen. Users have to track which format is being used for which matrix and I believe that was what the GP was originally complaining for.
- yosefk 3y agoAgreed, realistically you're going to either convert the data or give up on using the function rather than reimplementing it to support another data layout efficiently; while converting the code instead of the data, so to speak, is more efficient from the machine resource use POV, it can be very rough on human resources. (The article is basically about not having to give up in some cases where you can tweak the input parameters and make things work without rewriting the function; but it's not always possible)
- semi-extrinsic 3y agoTalking about rough on human resources, I take it you've never written iterative Krylov methods where matrices are in compressed sparse row (CSR) format? Because that's the kind of mental model capacity scientific programmers needed to have back in the days. People still do similarly brain-twisting things today. In this context, converting your logic between C and Fortran to avoid shuffling data is trivial.
- sa-code 3y agoWhat kind of support would you have hoped for?
- infogulch 3y agoA way to reinterpret a slice of size N as a multidimensional array with strides that are a factorization of N, including optional reverse order strides. Basically, do the stride bookkeeping internally so I can write an algorithm only considering the logic and optimize the striding order independently.
- Animats 3y agoThat's where you end up after heavy bikeshedding. Lots of features, terrible performance, as the OP points out.
- infogulch 3y agoI agree with you on sparse arrays and multidimensional slices, but this is basically the same as what you'd do manually. Saying that "track strides for me" is "lots of features" is a bit uncharitable.
- yosefk 3y agoFrom everything I'm seeing, it follows that Matlab & Fortran have been decimated by Python and C/C++ around 1990s and 2010s, respectively. Of course I could be wrong; any evidence of their still strong position will be greatly appreciated, doubly so evidence that this position is due to stride issues. (Of course Python provides wrappers to Fortran code, eg FITPACK, but this code specifically was mostly written in the 80s, with small updates in this century, and is probably used more thru the numpy wrappers, stride conversion issues and all, than thru its native Fortran interface)
- MobiusHorizons 3y agoI think pretty much all linear algebra libraries are still Fortran and are unlikely to ever be C because Fortran is legitimately faster than C for this stuff. I don't know if it has anything to do with strong opinions about how values are represented, I think it has more to do with lower overhead of function calling, but that is just repeating what someone told me about Fortran vs C in general, not necessarily applicable to BLAS libraries. Fortran at least used to be very common in heavy scientific computing, but I would bet that relies on GPUs or other accelerators these days.
- yosefk 3y agoThe question is how much new numeric code is written in Fortran vs C/C++. My guess is way below 10%, certainly if we measure by usage as opposed to LOC and I would guess by LOC as well. Is Fortran legitimately faster than C with the restrict keyword? Regardless of the function call cost diffs between the two - meaning, even if we assume Fortran is somehow faster here - there's no way numeric production code does enough function calls for this to matter. If Fortran was faster than C at any point in time I can only imagine pointer aliasing issues to have been the culprit and I can't imagine it still being relevant, but I am of course ready to stand corrected.
- eyegor 3y agoI don't think fortran is faster by language virtue, but it's certainly easier to scrap together high performance numeric fortran code. And ifort/aocc are amazing at making code that runs well on clusters, which is not a priority for any other domain. Fortran is absolutely still on top for modern numerics research code that involves clusters, talk to anyone who works in simulations at a national lab. If your code is mostly matrix math, modern fortran is very nice to work with. Emphasis on modern because maintaining 70s-80s numeric mathematician cowboy code is a ninth circle of hell. It has a bad rep for that reason.
- DarkUranium 3y agoI'm working towards my own language, and I'm sort of stuck on this issue, too: Namely: 1. Should the "default" (syntactically-sugar'd) arrays in the language (e.g. `int[]`) be restricted to simple contiguous storage, or should they also hold (potentially negative) stride, etc? 2. Should I have multidimensional arrays? (to be clear, I'm talking about contiguous blocks of data, not arrays-holding-pointers-to-arrays) 3. Should slicing result in a view, or a copy? (naturally, some of these options conflict) I'm honestly erring towards: 1. "fat" arrays; 2. multidimensional arrays; 3. slicing being views. This allows operations like reversing, "skipping slices" (e.g. `foo[::2]` in Python), even broadcasts (`stride=0`) to be represented by the same datastructure. It's ostensibly even possible to transpose matrices and such, all without actual copying of the data. But there are good arguments for the reverse, too. E.g. "fat" arrays need 1 more `size_t` of storage per dimension (to store the stride), compared to "thin" arrays. And a compiler can optimize thin ones much better due to more guarantees (for example, a copy can use vector instructions instead of having to check stride first). Plus "thin" arrays are definitely the more common scenario and it simplifies the language. So, yeah, still not quite sure despite liking the concept. One obvious option would be for `int[]` to be a thin array, but offering `DataView<int>` [1]. The problem with that is that people implementing APIs will default to the easy thing (`int[]`) instead of the more-appropriate-but-more-letters `DataView<int>`. Ah, dilemmas. [1] (not actual syntax, but I figured I'd use familiar syntax to get the point across)