Elegant breaking from nested loops

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. :frowning_face:

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.

I don’t know what you mean by that.
There is no error in the algorithm that creates an exception to normal operation.
It just needs to terminate those loops when prime > Math.isqrt(val)
You shouldn’t conceptualize that as an exception, it’s normal operational flow.

So I want to break out those loops, and would like a clean|faster way to do it.
Again, what I would like to do, is tell break to exit both loops, or have it jump|goto a specific point in the program to continue execution.

Sometimes doing things the old Fortran|BASIC way maybe are the best.

I see the error now, that I copied into my code: you weren’t raising the Break.new(:here). You should add the raise:

catch(:here) do
  prms.each_with_index do |resgroup, k|
    res.each_with_index do |prm_r, i|         
      ...
      raise Break.new(:here) if prime > Math.isqrt(val)
#     ^--- here
      ...
  end end end

Hope it’s clear now

Adding the raise reduced the times to ~64s, about the same as the nested breaks.

That implementation is overkill for what I want. I just want a break that will jump to the end of the outer loop (our more nicely to the end of any level within nested loops).

I understand but I don’t think we’ll ever add something like that.

1 Like

Goto’s in Nim.

https://forum.nim-lang.org/t/8963

In that discussion they arrive at the same discussion we have here. Basically, there’s no such thing as goto in Nim, and according to a member there shouldn’t be:

Nim’s optimizer does not understand control flow hiding in emit and is free to break your program. Instead of goto, use structured programming constructs like if and while (there is also return and break).

Then, another member proposed the use blocks, which allow for a directed break. This is what you need in your example, and differs significantly from the liberal goto.

Now, I went ahead and tried two things. First, I use a Proc to be able to return from it. This is in essence what a Nim block would do (but my solution doesn’t allow for multiple breaking points in different nested loops; only works for this case). Then, I implemented the throw/catch solution with an empty callstack as suggested by Ary. To my surprise, they’re equivalent in speed.

BTW, what takes 64s? Your example is immediate to me when calling sozpg(541).

3 Likes

That throw/catch code is really nice and concise. I would love to see that in the standard library.

Uh. On my AMD 3950x I get:

linus@dunk[prog] - (master *=): crystal run --release --mcpu znver2 sozpg.cr
throw/catch 308.38k (  3.24µs) (± 0.95%)  4.08kB/op   1.92× slower
     return 553.48k (  1.81µs) (± 1.15%)  4.01kB/op   1.07× slower
       meth 591.63k (  1.69µs) (± 0.92%)  3.96kB/op        fastest

Or in other words, the throw-catch variant take almost twice the time as the proc variant.

The fastest alternative is when actually extracting it to a basic method. The difference to the Proc version isn’t all that big though.

Code for meth example at

1 Can you include the original code that uses break for the baseline reference?

2 I also found throw|catch being much slower than break in the original code.
throw|catch has too much baggage here, because I don’t want to return a value of anything, all I want to do is jump|break|goto some location to resume execution. It’s completely for execution control, not for value passing.

3 Original assembly programming started out (and still must use) goto|jump because that’s the binary language|instruction set at the cpu level. That migrated to Fortran|Basic|etc because they were the next level above assembly back then.

Then came the Gods of structured programming who decreed thy shall not have goto in any language; except C still has|needs|uses them, et al.

Sometimes, sometimes, if you just need|want to goto|jump to some location then you should be able to do that in an elegant way. The hardware doesn’t care, and is even designed to do just that.

1 Like

1: Well, your message with those included three different variants. The first didn’t compile, but the second is equally fast as the method variant - sometimes 1.01 faster, sometimes 1.01 slower. I have not checked the generated code, it is quite possible that the method is inlined by the compiler. In any case, no difference that I could see.

3: Here, we will have to disagree. It is kinda necessary to have goto in C because they have no other sane way to do error handling and resource cleanup, but as more modern came around that solved those problems in better ways goto is no longer needed.

Oh and by the way: If you have an idea of how many primes there will be, I can recommend setting an initial_capacity of the prime list that is close to the expected number. That gives an additional 27%, though it may be an artifact of the smaller example - running with bigger numbers will naturally require relatively speaking fewer resizings.

3 Likes

1: I meant to run my original code and compare the other methods times against it.

3: Yes, this is an ideological conflict, not a technical conflict preventing doing it. The compiler obviously determines the execution resume points for every loop. In fact, a break is just a goto to the execution resume point for just the loop it’s in. For multiple nested loops the compiler determines the execution resume points for each (it has to for the program to run), so an elegant break would provide a way to tell the compiler which loop execution resume point (which it already knows) to break to. Not wanting to do it is not the same as not being able to do it.

The worst case for the possible prime candidates (pc)s is the number of generator residues times the number of residues groups upto end_num. We can know exactly how many pcs there are, but their primes/pcs ratio increases with each generator, and depending on the implementation, it may|not be worth it to preallocate that amount of memory for the primes. I guess if you know before hand the range of numbers you are processing always contains a certain max number of primes it may be worth doing.

Some very respectable languages, like Rust, Ada, Nim and D have simple labeled loops that allows one to break out of nested loops. :nerd_face: It would be pretty darn cool if Crystal had something similar.

D

import std.stdio;

void main() {
outer: for (int i = 0; i < 2000; ++i)
{
  writeln(i);
    for (int j = 0; j < 2000; ++j)
      {
        writeln(j);
        if (i + j == 3145)
          writefln("%s, %s\n", i, j);
          writeln("I'm inside the nested loops");
        break outer;
      }
  }
  writeln("I'm outside the nested for loops.");
} 

Rust:

#![allow(unreachable_code, unused_labels)]

fn main() {
    'outer: loop {
        println!("Entered the outer loop");

        'inner: loop {
            println!("Entered the inner loop");

            // This would break only the inner loop
            //break;

            // This breaks the outer loop
            break 'outer;
        }

        println!("This point will never be reached");
    }

    println!("Exited the outer loop");
}

Ada

procedure Show_Inner_Loop_Exit is
   pragma Warnings (Off);

   Cond : Boolean := True;
begin

   Outer_Processing : loop

      Inner_Processing : loop
         exit Outer_Processing when Cond;
      end loop Inner_Processing;

   end loop Outer_Processing;

end Show_Inner_Loop_Exit;

Nim

# This code will print "outer"
block outer:
  while true:
    block inner:
        while true:
            break inner
            #break outer
    echo "inner"
    break outer

echo "outer"

See also

1 Like

Very cool! I’m looking over a few other languages both old and new to see which support breaking nested loops easily. I guess it would be quicker for me to just to go to Rosetta Code, but the site has been rather unreliable lately and is currently down. :confused:

Odin

package main
import "core:fmt"

main :: proc () {
    outer: for i in 0..<2000 {
        fmt.println(i);
        for j in 0..<2000 {
            fmt.println(j);
            if i + j == 3145 {
                fmt.println(i, ", ", j);
                fmt.println("I'm inside the nested loops");
                break outer;
            }
        }
    }
    fmt.println("I'm outside the nested for loops.")
}

V

outer: for i := 4; true; i++ {
	println(i)
	for {
		if i < 7 {
			continue outer
		} else {
			break outer
		}
	}
}

Zig

test "nested break" {
    outer: while (true) {
        while (true) {
            break :outer;
        }
    }
}

test "nested continue" {
    var i: usize = 0;
    outer: while (i < 10) : (i += 1) {
        while (true) {
            continue :outer;
        }
    }
}

Go also has the concept of labeling loops and breaking from them. It is sometimes the most consistent, concise and simple way to write the code.

I agree adding it to crystal would be good and no harm. If not added a better alternative should be presented. The solution should not harm the performance for obvious reasons.

1 Like