# Elegant breaking from nested loops

Another way to do it is to leverage the ability for `break`/`loop` to return a value. E.g.

``````loop do
b = loop do
break true if true
end

break if b
end
``````

Similar to your `flag` example, but a bit more concise/robust.

1 Like

Yeh, but the desire is to not use two break points.

As I stated above, a method, and then using `return` is the easiest way to accomplish that.

``````def mark_nonprimes(nonprimes, residues, val, md, bitn, kmax)
breakpoint = Math.isqrt(val)
nonprimes.each_with_index do |resgroup, k|# for each kth residue group
residues.each_with_index do |prime_residue, i|  # check for each ith residue in resgroup
next if resgroup & (1 << i) != 0 # if bit location a prime
prime = md * k + prime_residue           # numerate its value, store if in range
return if prime > breakpoint # exit loop when it's > sqrtN
residues.each do |ri|                 # mark prime's multiples in primes
kn, rn = (prime_residue * ri - 2).divmod(md) # cross-product resgroup|residue
prime_multiple = k * (prime + ri) + kn    # mark prime’s multiples starting here
while prime_multiple < kmax;
nonprimes[prime_multiple] |= bitn[rn]
prime_multiple += prime
end
end
end
end
end
``````

I also took the liberty to clarify up the variable naming a bit, but a lot more could be done there.

3 Likes

Thanks for your example. But again, I don’t want to make the code more complex.
It’s clear there’s no simple(r) way to break out of nested loops than to use nested breaks, or my original code that only created one loop to break out of.

Maybe someone from core team can speak to why `throw`/`catch` from Ruby was not added to Crystal.

Also related: https://github.com/crystal-lang/crystal/issues/11658.

1 Like

I suppose this could be solved with `throw`/`catch` but really a more direct solution would be a nesting value for `break`. In PHP for example, you can pass a number to `break` which determines how many nested levels of loops it should break.

`throw`/`catch` is often critizised for pulling code out of context and making it hard (for humans) to follow control flow.

3 Likes

I was never a big fan of the pass the number of loops to break out of approach, it seems too easy to mess up when moving code around and encourages deep loop nesting in the first place. I’m also unsure how well it fits and interacts with the fact that Crystal loops are really just repeatedly called blocks.

I actually like when a language forces me to solve this by extracting an inner loop or two into a method to achieve the breaking using return. It usually leads to cleaner/easier to follow code IME. Also IME in a language with a lot of list and map data manipulation methods in the standard library like Crystal it’s often easy to avoid deeply nested loops for a more map/reduce focused kind of approach.

8 Likes

There’s also the thing that if we allow breaking from an inner loop then we need to think about how the type inference/flow changes. All type inference done up until the “break” point is carried over outside, which makes the compiler and the language harder to implement and understand.

2 Likes

`break` can be extended, without breaking code, by, as suggested, using it as

`break 2 if cond`

where 2 is the number of nested loops, with default as 1, or explicitly like

`break here: if cond`

where `here:` is a marker in the code to begin execution from (basically a `GOTO`).

This is very useful for multidimensional numerical processing algorithms, where if some point in an inner loop requires aborting the whole process, it would make Crystal very attractive to such applications, to be able to use short and clear idiomatic loop structures, like in my example, and have a language defined way to jump out of any level of nesting in a clean, non-hacky, way.

This would have definitely increased my programming productivity to write that top level looping process like the bottom (where it doesn’t `break`). But I wrote it originally as shown because it was the simplest way to get what I needed within 1 loop.

But think if you’re doing something like a 3 dimensional graphic algorithm, et al. At least initially, to establish functional correctness, you want to mimic the canonical definition of the algorithm as much as possible to establish you’ve satisfied all the edge cases. Once it produces correct results, then you can tear it apart to try to optimize it (speed|memory). But in many applications an idiomatic clean version is all that’s needed, especially if you factor in code maintainability and documentation.

I see being able to idiomatically jump out of any level of loop nesting an attractive feature for Crystal to people doing these type of algorithms, and in general.

1 Like

Will something like the following work for you? Caveat: it breaks to the specific place but holds no value. But perhaps for your uses you can adapt my solution…

``````class Break < Exception
getter symbol : Symbol

def initialize(@symbol : Symbol)
end
end

def catch(symbol : Symbol)
begin
yield
rescue e : Break
raise e unless e.symbol == symbol
end
end

i = 0
j = 0

catch(:here) do
while i < 1_000
catch(:there) do
while j < 1_000
case rand 100
when 1
raise Break.new(:here)
when 2
raise Break.new(:there)
end
j += 1
end
end
i += 1
end
end

p! i, j
``````

This said, as mentioned already, `goto`s have several issues, even if there are some valid uses.

5 Likes

When @matthewmcgarvey was porting Roda to Crystal he actually implemented `throw` / `catch` because that’s how Roda bails on processing the request. He uses `LibUnwind` directly to avoid generating a stack trace, which IIRC was the most expensive part of raising an exception, so it should theoretically be lighter-weight than a typical `raise`.

I don’t know how well it works in practice because I haven’t tried it, but I remember he did check it pretty thoroughly at the time. But it does exist if you want to try it.

3 Likes

If you want to avoid a stack trace, there’s no need to use libunwind directly. You just need to assign a value to the exception’s `callstack` property before raising.

3 Likes

Found the thread where it was discussed before. I couldn’t remember the details.

I tried it, and it works. But - `catch :here` || `catch(:here)` - produces error.

``````In catchtest.cr:59:3

59 | catch :here
^----
Error: 'catch' is expected to be invoked with a block, but no block was given

In catchtest.cr:59:3

59 | catch(:here)
^----
Error: 'catch' is expected to be invoked with a block, but no block was given
``````

But these work - `catch :here {}` || `catch(:here) {}`

Could make visually nicer, something like this:

``````Break.new(:here)  -> throw :here
catch :here {} -> catch :here
``````

Otherwise it seems to work, at lease in this example.
This definitely would have made writing the original code a snap.
I would urge adding this capability into the language!

Here’s the test code (made `sozpg` simpler for testing purposes).

``````class Break < Exception
getter symbol : Symbol

def initialize(@symbol : Symbol)
end
end

def catch(symbol : Symbol)
begin
yield
rescue e : Break
raise e unless e.symbol == symbol
end
end

def sozpg(val)
md, rscnt = 30u64, 8
res  = [7,11,13,17,19,23,29,31]
bitn = [0,0,0,0,0,1,0,0,0,2,0,4,0,0,0,8,0,16,0,0,0,32,0,0,0,0,0,64,0,128]

kmax = (val - 2) // md + 1
prms = Array(UInt8).new(kmax, 0)

prms.each_with_index do |resgroup, k|
res.each_with_index do |prm_r, i|
next if resgroup & (1 << i) != 0
prime = md * k + prm_r
Break.new(:here) if prime > Math.isqrt(val)
res.each do |ri|
kn, rn = (prm_r * ri - 2).divmod md
kpm = k * (prime + ri) + kn
while kpm < kmax; prms[kpm] |= bitn[rn]; kpm += prime end
end end end
catch :here {}
primes = [2, 3, 5] of UInt64
prms.each_with_index do |resgroup, k|
res.each_with_index do |r_i, i|
primes << md * k + r_i  if resgroup & (1 << i) == 0
end end
primes
end

puts (primes = sozpg(541)).size
print primes
``````

https://play.crystal-lang.org/#/r/cqdy

Sorry, I missed to explain my code and that lead you to the wrong application.

In order to work properly, the code must be enclosed in a block. The symbol is not a label in a goto sense, just a mark to say “if the code that the block is executing raises this particular label, then rescue it, otherwise re-raise it”. Probably the example you’re executing isn’t raising the error (`prime` is never greater than `Math.isqrt(val)`? Commenting that line produces the same result).

The correct rewrite should be:

``````def sozpg(val)
md, rscnt = 30u64, 8
res  = [7,11,13,17,19,23,29,31]
bitn = [0,0,0,0,0,1,0,0,0,2,0,4,0,0,0,8,0,16,0,0,0,32,0,0,0,0,0,64,0,128]

kmax = (val - 2) // md + 1
prms = Array(UInt8).new(kmax, 0)

catch(:here) do
prms.each_with_index do |resgroup, k|
res.each_with_index do |prm_r, i|
next if resgroup & (1 << i) != 0
prime = md * k + prm_r
Break.new(:here) if prime > Math.isqrt(val)
res.each do |ri|
kn, rn = (prm_r * ri - 2).divmod md
kpm = k * (prime + ri) + kn
while kpm < kmax; prms[kpm] |= bitn[rn]; kpm += prime end
end end end
end
primes = [2, 3, 5] of UInt64
prms.each_with_index do |resgroup, k|
res.each_with_index do |r_i, i|
primes << md * k + r_i  if resgroup & (1 << i) == 0
end end
primes
end
``````

Ah that explains the slow times.

After running some benchmarks, the original code took ~50s, the code using nested `break` statements took ~60s, and my implementation using code your took ~255s.

I’ll try the way you just showed and see what happens.

Nothing is going to be faster than your original code.

@asterite apparently so.

I reran it using @beta-ziliani version and it took ~266s too, so it seems it’s not jumping out of the inner loop?

I think @straight-shoota suggestion of doing it PHP’s way by giving the number of loops to back out of would be the cleanest visually and functionally. Oh well.

I have one more trick to try, to do the sieve part in parallel, just for my own education, which this was mostly about anyway.

There’s a part you missed from my last comment: your code isn’t raising, so there’s a problem with the logic of the algorithm.