Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Create a fast operative for 'for' #433

Open
masak opened this issue Oct 10, 2022 · 2 comments
Open

Create a fast operative for 'for' #433

masak opened this issue Oct 10, 2022 · 2 comments

Comments

@masak
Copy link
Owner

masak commented Oct 10, 2022

I wrote the following straightforward code that prints a chessboard:

(set N 13)

(set board (array (list N N) \.))
(pr "ready now to print board" \lf)

(pr "  ")
(for i 1 N
  (pr " " (nchar (+ i 96))))
(pr \lf)

(for i 1 N
  (for j 2 i
    (pr " "))
  (when (< i 10)
    (pr " "))
  (pr i " ")
  (for j 1 N
    (pr " " (board i j)))
  (pr \lf))

(pr \lf)

Guess how long it takes to run? 28 minutes!

% time bel hex-board.bel
ready now to print board
   a b c d e f g h i j k l m
 1  . . . . . . . . . . . . .
  2  . . . . . . . . . . . . .
   3  . . . . . . . . . . . . .
    4  . . . . . . . . . . . . .
     5  . . . . . . . . . . . . .
      6  . . . . . . . . . . . . .
       7  . . . . . . . . . . . . .
        8  . . . . . . . . . . . . .
         9  . . . . . . . . . . . . .
         10  . . . . . . . . . . . . .
          11  . . . . . . . . . . . . .
           12  . . . . . . . . . . . . .
            13  . . . . . . . . . . . . .

bel hex-board.bel  1673.68s user 2.84s system 99% cpu 27:59.15 total

Just now I also created a version of the script containing only the for loops. I'm running it now, timing it. The fact that I'm still typing these words as it continues to run shows how unacceptably slow for is right now.

(set N 13)

(for i 1 N)

(for i 1 N
  (for j 2 i)
  (for j 1 N))

I don't foresee any big issue in creating a fast operative for for. #412 doesn't mention it among the ones it decides to skip because it's hard.

Ah, here:

% time bel only-for-hex-board.bel
bel only-for-hex-board.bel  188.32s user 0.66s system 99% cpu 3:09.80 total

Three minutes. Yes, that would still be a really nice time win. Seems that would still leave 25 minutes for my hex board, but at least it wouldn't be the for loops' fault.

@masak
Copy link
Owner Author

masak commented Oct 11, 2022

I just created and ran a version of the code without the for loops but with all the rest of the code. It does indeed take 25 minutes. I'm now a little bit curious what it is that takes such time...

  • Some nchar calls
  • A bunch of board lookups

I made yet another version without these two, and that takes 1.6 seconds. So, yeah. Slow.

When I put back the nchar calls, I get 46 seconds. Which would assign ~24 minutes to the board lookups.

@masak
Copy link
Owner Author

masak commented Oct 11, 2022

Looking into #200 for evidence of the slowness of arrays, I found a similar comment I had made about four months ago. But back then I wasn't using arrays, so I mostly got the three-minute slowdown of for loops.

Onwards towards faster programs!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant