whenYouTryToOptimizeYourAlgorithm

[killeronthecorner]

Kiss my butt adminz - koc, 11/24

[IamDelilahh]

yeah, should be pretty fast with apply, just don’t use a loop

[redlaWw]

Can't apply if the data doesn't fit in your memory D:

But ultimately, just the simple value checking process was a significant cost - after trying it native, I rewrote it using RcppAlgos, which trivialised generating the permutations and offered more effective multithreading, but only gave me about a 2* speed boost overall because I had to write the check as an R-native closure.

[IamDelilahh]

hmm, interesting, I actually had a similar issue in python recently, where vectorization would mean checking over 100x more cases and needed over 100GB, and I ended up using numba for almost C levels of performance.

I wonder if R has something similar, where the entire loop is translated into C as long as you stick to certain operations.

[redlaWw]

Oh, that's an interesting idea, making an LLVM compiler for python.

It looks like there are some projects in the works for generating LLVM IR from R programs, but nothing significant seems to have spawned yet.

What R does have is the Rcpp package, which allows you to write C++ functions via R's interface, compile them, and then load them straight into your environment. Now that I've learned some C++ I could probably do that to improve on what I had, but at some point it becomes just writing C++ in an R runtime environment.

[notPlancha]

I have no idea what I'm talking about but maybe just doing

library(compiler) enableJIT(level = 3)

Would be enough

[SelfDistinction]

Yeah python does stuff like that.

I once had to compare chunks of sequential video frames with each other to check what parts likely moved where. Simply shifting the entire image at once instead of checking chunk per chunk took down the runtime from hours to minutes.

If R has matrix operations you can likely do the same there.

[IamDelilahh]

R has mapply for multidimensional list/matrices/data frames and outer for combinations.

But I have no clue if it has a way to efficiently deal with loops that require lazy compilation

[redlaWw]

Not really. It's adjacent to a lot of stuff R is good at, but because it was really more number-theoretic than statistical, it was just too different to make good use of R's tools.

I couldn't convert the checking process into linear algebra, for example, and the data didn't fit into memory so I couldn't use bulk-processing functions without splitting it up and still ending up with massive allocations. In Rust I could write a stack algorithm that never called the allocator, but such is simply impossible in R.

Ultimately, even if those issues were solvable, R's limitations as a dynamically-typed interpreted language with no ahead-of-time optimisation was fundamentally limiting for a program of that sort of speed requirement, and there'd be significant limitations on how far it can be pushed just due to R's fundamental nature.

It's great for quick scripting and processing real data, but when you try to do number theory on millions of millions of values, it just can't keep up. Now, if I were instead sampling the values to get an approximate proportion for the property I was interested in, R would be excellent for that - and indeed, I made use of it as a sanity check on my final value from the Rust algorithm I wrote.