;redcode
;name FastSpawnGeneratorV2
;author Skybuck Flying
;version 2
;history version 1 and 2 created on 7 december 2007
; version 2:
;
; Tested with 100 and working ok
;
; 214 cycles needed. 8% improvement
probably more optimization can be
done
;
;
; Let's write an optimized spawn generator to try and beat at least John's
spawn generator lol.
;
; I think I can optimize it by using dual counters so that the mov
instructions can move twice as many data into the comparators etc.
;
;
; version 1:
; Tested with 100 and working ok
; 235 cycles needed to generate 100 threads.
; Code/comments still a bit messy but it's working ! =D
;
; Let's write a faster spawn creator.
;
; Hello,
;
; Listen if you want to spawn a number of threads then do the following:
;
; First substract 1 from the number of threads.
;
; Then determine where it lies on the binary scale for example
; 1-2-4-8-16-32-64-128-256-512-1024
;
;For example (101-1) = 100 threads to be created to get 101 threads lies
;between 64 and 128.
;
;Simple idea, start with 1, multiply it by 2, keep multiplieing it by 2
until
;it's greater than the number of threads.
;
;Now divide it once and you have something which you can use to find the
;binary number for 100.
;
;Call it the divisor. For example for 100 the divisor starts with 64.
;
;Here's the rest of algo:
;
;Divide Number of Threads (100) by the divisor (64).
;
;If it can divide it gives 1 if not it gives a 0.
;
;Now comes the interesting part.
;
;For a 1, the number of threads need to dubbel.
;For a 0, the number of threads need to dubbel-1.
;
;Depending on the outcome, dubbel or dubbel-1 the threads.
;
;To dubbel use spl 1
;To dubbel-1 use mov spawn, 0 (spawn is spl 1)
;
;Then make all threads jump to generated instruction as described in the two
;lines above.
;
;So for a 1:
;
;spl 1 should be executed.
;
;So for a zero
;
;mov spawn, 0 will be executed for the first thread.
;all other threads will execute
;spl 1, 0
;
;This has the effect that one less thread will be created which is exactly
;what it should.
;
;Now divide the divisor by 2 and repeat the loop, until the divisor is zero.
;
;Here is an example:
;
;100 div 64 = 1, remainder 35
;36 div 32 = 1, remainder 4
;4 div 16 = 0, remainder 4
;4 div 8 = 0, remainder 4
;4 div 4 = 1, remainder 0
;0 div 2 = 0, remainder 0
;0 div 1 = 0, remainder 0
;0 div 0 = death of thread. you could try to avoid it or use it to your
;adventage to kill off any calculating thread or so.
;
;binary 1100100 = 100
;
;Now you have an algorithm to extract the binary one's and zero's from the
;number 100.
;
;And thus you can create a nice spawning program which will execute fast.
;
;The spawning program should look something like:
;spl 1
;spl 1
;mov -1, 0
;mov -1, 0
;spl 1
;mov -1, 0
;mov -1, 0
;jmp 0
;
;An alternative method (untested but will probably work just as well):
;
;spl 1
;spl 1
;mov SplInstruction, 0
;mov SplInstruction, 0
;spl 1
;mov SplInstruction, 0
;mov SplInstruction, 0
;jmp 0
;SplInstruction spl 1
;After this code has been executed there will be 100 threads created plus
the
;main thread so 101 threads ! nice eh !
;
;Now the only thing to do is for example write some nice redcode code which
;implements the algorithm with div's, mod's and such.
; modified in v2
mov.a #99, NumberOfThreadsToSpawn ; number of threads to spawn
; Algorithm:
;
; Step 1: start with 1 and keep multiplieing it until it's greater then the
number of threads to spawn
; the multiplieing result will ultimately be used as a divisor so the
variable will be called "Divisor"
mov #1, Divisor
Multiplier mul #2, Divisor
; mov.b $Divisor, Comparison
; mov.ba $NumberOfThreadsToSpawn, Comparison
; Divisor now in B
; NumberOfThreadsToSpawn now stored in A
; both above replaced with optimization:
mov.f $DualData, Comparison
; as long as divisor is equal or more then number of threads multiply it
; slt skips next instruction if less than, so it executes next instruction
of equal or more than.
; slt can be thought of as: execute next instruction if b >= a otherwise
skip
Comparison slt #0, #0
jmp Multiplier
; now we need to divide the divisor once
div #2, Divisor
;
; Step 2: Divide the NumberOfThreadsToSpawn by the divisor, the outcome
indicates a 1 for spl 1 or mov spl 1, 0 for a zero.
; then calculate the remainder for number of threads to spawn
; then divide the divisor by 2, repeat until divisor is zero
Step2
; mov.ba $Divisor, Divider
; mov.b $NumberOfThreadsToSpawn, Divider
; both above replaced with optimization:
mov.x $DualData, Divider
Divider div #0, #0
; look at result, generate instruction etc
; look at the result,
; if it's a 1 we need to add instruction: spl 1, to the spawn program
; if it's a 0 we need to add instruction: mov doubleinstruction, 0 to the
spawn program
jmz.b StepDoubleMinusOne, Divider
StepDouble:
mov DoubleInstruction, >SpawnProgramPointer
jmp Skip
StepDoubleMinusOne:
mov DoubleMinusOneInstruction, >SpawnProgramPointer
Skip
; calculate the remainder for the number of threads to spawn
; mov.ba $Divisor, Modder
; mov.b $NumberOfThreadsToSpawn, Modder
; both above replaced with optimization:
mov.x $DualData, Modder
Modder mod #0, #0
; move result back into number of threads to spawn
; modified in v2
mov.ba Modder, NumberOfThreadsToSpawn
; divide the divisor by 2
mov.b $Divisor, Divider2
Divider2 div #2, #0
; move result back into the divisor
mov.b Divider2, Divisor
; repeat
jmn Step2, Divisor
; add a spinner to the spawn program to keep the threads spinning to
demonstrate how many there are
; could be handy for final programs as well. probably would have to alter
jump instruction to compensate for generated program length
; ignored for now... just jump to end of program for now
; mov SpinnerInstruction, >SpawnProgramPointer
; jump to spawn program to execute it
; jmp @SpawnProgramPointer ; wrong offset ignored for now, might not even
matter as long as one knows where to jump to at begin of the algo
jmp EndOfProgram
DoubleInstruction spl $1, 0
DoubleMinusOneInstruction mov DoubleInstruction, 0
SpinnerInstruction jmp $0, $0
; NumberOfThreadsToSpawn dat $0, #0
; Divisor dat $0, #0
; replaced with dual data storage:
NumberOfThreadsToSpawn
Divisor
DualData dat #0, #0
; NumberOfThreadsToSpawn will be in A
; Divisor will be in B
SpawnProgramPointer dat $0, #EndOfProgram
EndOfProgram
FAQ
Profile
Private Messages
Log in
