# How to make this faster? **URL:** \ **Category:** Help & Support\ **Created:** [January 22, 2024, 9:55am UTC](https://forum.crystal-lang.org/t/how-to-make-this-faster/6357 "2024-01-22T09:55:07Z")\ **Posts on this page:** 11\ **Page:** 1
**Author:** ![extgcd](https://avatars.discourse-cdn.com/v4/letter/e/a3d4f5/32.png) [@extgcd](https://forum.crystal-lang.org/u/extgcd)\ **Post date:** [January 22, 2024, 9:55am UTC](https://forum.crystal-lang.org/t/how-to-make-this-faster/6357/1 "2024-01-22T09:55:07Z")
I have a toy program for generating first N 100-smooth numbers (i.e. each has all its prime factors less than 100). The Crystal version runs in about 1.2s while the Rust version runs in less than .5s. So rust version is more than 2x faster. My other programs that use arrays(sieve, totients, etc) have around the same perf as their Rust versions but this one isn’t. Crystal ```auto def get_100_smooths(limit : UInt32) : Array(UInt32) primes = Array(UInt32){2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97} sp_idxs = Array.new(primes.size, 0) cands = primes.dup smooths = Array.new(limit.to_i32 + 1, 1u32) 1.upto(to: smooths.size - 1) do |si| smooths[si] = cands.min 0.upto(to: cands.size - 1).select { |ci| cands[ci] == smooths[si]}.each do |ci| sp_idxs[ci] += 1 cands[ci] = smooths[sp_idxs[ci]] * primes[ci] end end smooths end elapsed = Time.measure do puts get_100_smooths(5_000_000u32).last end puts elapsed ``` Rust ```auto fn get_100_smooths(lim: u32) -> Vec { const PRIMES: [u32; 25] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]; let mut sp_idxs = [0usize; PRIMES.len()]; let mut cands = PRIMES; let mut smooths = vec![1u32; (lim + 1) as usize]; (1..smooths.len()).for_each(|si| { smooths[si] = *cands.iter().min().unwrap(); (0..cands.len()).for_each(|ci| { if cands[ci] == smooths[si] { sp_idxs[ci] += 1; cands[ci] = smooths[sp_idxs[ci]] * PRIMES[ci]; } }); }); smooths } fn main() { let timer = std::time::Instant::now(); let smooths = get_100_smooths(5_000_000); println!("{:?}", smooths.last()); println!("{:?}", timer.elapsed()); } ``` These were ran on a aarch64-linux-android through termux. Maybe unrelated: When I compile a rust version (this or the toy programs) compilation takes less than 2s. But with Crystal it takes about 15s. The part “Codegen (bc + obj)” takes about 13s. Is that normal? These are small Crystal programs and 15s doesn’t seem appropriate. ---
**Author:** ![straight-shoota](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/straight-shoota/32/36_2.png) [@straight-shoota](https://forum.crystal-lang.org/u/straight-shoota)\ **Post date:** [January 22, 2024, 11:15am UTC](https://forum.crystal-lang.org/t/how-to-make-this-faster/6357/2 "2024-01-22T11:15:46Z")
I’m not very experienced with Rust, but it looks like your Rust implementation is using some array types, with a constant, static size. The equivalent in Crystal would probably be `StaticArray` (I’m not entirely sure about the semantic details in Rust). Another difference in the implementation is that the inner loop uses an interator in Crystal, while in Rust it’s just a `for_each`. Using the same shape in Crystal would avoid allocating an iterator, thus free up a lot of time spent allocating and GCing. This is similar to what I wrote in [Why so big differences? - #3 by straight-shoota](https://forum.crystal-lang.org/t/why-so-big-differences/6348/3) If you want best performance, try to avoid `Iterator` if possible. ---
**Author:** ![zw963](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/zw963/32/1623_2.png) [@zw963](https://forum.crystal-lang.org/u/zw963)\ **Post date:** [January 22, 2024, 4:47pm UTC](https://forum.crystal-lang.org/t/how-to-make-this-faster/6357/3 "2024-01-22T16:47:36Z")
I test on my local laptop (AMD Ryzen 7 7840HS), Rust version slower than Crystal version. ```sh ╰─ $ cr build --release a.cr ╰─ $ ./a 2998212735 00:00:00.664267188 ``` ```sh ╰─ $ rustc -C target-cpu=native a.rs -o b ╰─ $ ./b Some(2998212735) 2.838247485s ``` Is it possible use Rust compiler is incorrect? ---
**Author:** ![extgcd](https://avatars.discourse-cdn.com/v4/letter/e/a3d4f5/32.png) [@extgcd](https://forum.crystal-lang.org/u/extgcd)\ **Post date:** [January 23, 2024, 12:03am UTC](https://forum.crystal-lang.org/t/how-to-make-this-faster/6357/4 "2024-01-23T00:03:26Z")
I removed ‘select’ from the inner loop and time now is around Rust’s . I also removed it from some of my codes and some had noticeable perf improvement while others didn’t (like sieve, maybe because its just checking for truthiness). It’s a pity that I cannot use Iterators more freely since they can really shorten code(reduce locs) while being clear. Thanks for your time! ---
**Author:** ![extgcd](https://avatars.discourse-cdn.com/v4/letter/e/a3d4f5/32.png) [@extgcd](https://forum.crystal-lang.org/u/extgcd)\ **Post date:** [January 23, 2024, 12:07am UTC](https://forum.crystal-lang.org/t/how-to-make-this-faster/6357/5 "2024-01-23T00:07:10Z")
I compiled rust with ‘cargo clean && cargo r -r’. And it also passes ‘cargo t’, without ‘-r’. That difference is really weird. PS: I’m not sure but I don’t think I see an optimization flag in your Rust compile command. ---
**Author:** ![jzakiya](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/jzakiya/32/278_2.png) [@jzakiya](https://forum.crystal-lang.org/u/jzakiya)\ **Post date:** [January 23, 2024, 1:36am UTC](https://forum.crystal-lang.org/t/how-to-make-this-faster/6357/6 "2024-01-23T01:36:10Z")
FYI. I made your original Crystal code almost twice as fast on my system. Linux kernel 6.5.13, Crystal 1.11.2, AMD Ryzen 9 5900HX Here’s a more optimized Crystal version. ```auto def get_100_smooths(limit : UInt32) : Array(UInt32) primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] of UInt32 sp_idxs = Array.new(primes.size, 0) cands = primes.dup smooths = Array.new(limit.to_i32 + 1, 1u32) (1...smooths.size).each do |si| smooths[si] = cands.min cands.size.times do |ci| if cands[ci] == smooths[si] sp_idxs[ci] += 1 cands[ci] = smooths[sp_idxs[ci]] * primes[ci] end end end smooths end elapsed = Time.measure do puts get_100_smooths(5_000_000u32).last end puts elapsed ``` Typical time differences. ```auto ➜ crystal run --release forumcode_orig.cr 2998212735 00:00:00.654938502 ➜ crystal run --release forumcode_opt.cr 2998212735 00:00:00.385553579 ``` ---
**Author:** ![extgcd](https://avatars.discourse-cdn.com/v4/letter/e/a3d4f5/32.png) [@extgcd](https://forum.crystal-lang.org/u/extgcd)\ **Post date:** [January 23, 2024, 2:44am UTC](https://forum.crystal-lang.org/t/how-to-make-this-faster/6357/7 "2024-01-23T02:44:00Z")
This is about the same as my modified code after following @straight-shoota’s suggestions. I removed ‘select’ and used an ‘if’. I also used a StaticArray for ‘primes’, ‘sp\_idxs’ and ‘cands’. Your version runs in around 0.7s while my modified version runs in around 0.5s. It’s really a pity Iterators aren’t as optimized as their imperative equivalents. ---
**Author:** ![jzakiya](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/jzakiya/32/278_2.png) [@jzakiya](https://forum.crystal-lang.org/u/jzakiya)\ **Post date:** [January 23, 2024, 3:46am UTC](https://forum.crystal-lang.org/t/how-to-make-this-faster/6357/8 "2024-01-23T03:46:38Z")
With `StaticArray`. ```auto def get_100_smooths(limit : UInt32) : Array(UInt32) primes = UInt32.static_array(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) sp_idxs = StaticArray(UInt32, 25).new(0) cands = primes.dup smooths = Array.new(limit.to_i32 + 1, 1u32) (1...smooths.size).each do |si| smooths[si] = cands.min cands.size.times do |ci| if cands[ci] == smooths[si] sp_idxs[ci] += 1 cands[ci] = smooths[sp_idxs[ci]] * primes[ci] end end end smooths end elapsed = Time.measure do puts get_100_smooths(5_000_000u32).last end puts elapsed ``` Slightly faster times. ```auto ➜ crystal run --release forumcode_opt.cr 2998212735 00:00:00.331489153 ``` ---
**Author:** ![jzakiya](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/jzakiya/32/278_2.png) [@jzakiya](https://forum.crystal-lang.org/u/jzakiya)\ **Post date:** [January 23, 2024, 5:43am UTC](https://forum.crystal-lang.org/t/how-to-make-this-faster/6357/9 "2024-01-23T05:43:57Z")
Just for newbies, and to show another alternative. A smidgen less code. Has same performance. ```auto def get_100_smooths(limit : UInt32) : Array(UInt32) primes = UInt32.static_array(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) sp_idxs = StaticArray(UInt32, 25).new(0) cands = primes.dup smooths = Array.new(limit.to_i32 + 1, 1u32) (1...smooths.size).each do |si| smooths[si] = cands.min cands.size.times do |ci| next unless cands[ci] == smooths[si] sp_idxs[ci] += 1 cands[ci] = smooths[sp_idxs[ci]] * primes[ci] end end smooths end ``` ---
**Author:** ![zw963](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/zw963/32/1623_2.png) [@zw963](https://forum.crystal-lang.org/u/zw963)\ **Post date:** [January 23, 2024, 8:12am UTC](https://forum.crystal-lang.org/t/how-to-make-this-faster/6357/10 "2024-01-23T08:12:13Z")
> [@extgcd](#): > > It’s a pity that I cannot use Iterators more freely since they can really shorten code(reduce locs) while being clear The select never shorter you code instead of use only loop in this case. In fact, use select Iterator with a loop is consider rarely, 10 loops with if/else in it always faster than 4 loops nested 4 select, i hope you understand what I mean . ---
**Author:** ![zw963](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/zw963/32/1623_2.png) [@zw963](https://forum.crystal-lang.org/u/zw963)\ **Post date:** [January 23, 2024, 8:20am UTC](https://forum.crystal-lang.org/t/how-to-make-this-faster/6357/11 "2024-01-23T08:20:52Z")
next in the external Iterator(loop), this may be the most common usage.