From 26bce7119200f37f8b9f3ddc1a2c76c85f7c88be Mon Sep 17 00:00:00 2001 From: Charlie Stanton Date: Fri, 21 Apr 2023 12:51:25 +0100 Subject: Changes the implementation of Atomise and Compound to no longer use goroutines This results in a massive performance boost, ~4x speedup --- main/command.go | 13 +--- subex/arithmetic.go | 10 ++-- subex/main.go | 13 ++-- walk/walk.go | 167 ++++++++++++++++++++-------------------------------- 4 files changed, 80 insertions(+), 123 deletions(-) diff --git a/main/command.go b/main/command.go index 9554f9d..136fb26 100644 --- a/main/command.go +++ b/main/command.go @@ -54,19 +54,12 @@ func (cmd DeletePathCommand) exec(state *ProgramState) { } func runSubex(state subex.SubexState, in []walk.WalkValue) (out []walk.WalkValue, error bool) { - valueStream := make(chan walk.WalkValue) - go func(in []walk.WalkValue, out chan<- walk.WalkValue) { - for _, value := range in { - out <- value - } - close(out) - }(in, valueStream) - atomStream := walk.Atomise(valueStream) - atomsOut, error := subex.RunTransducer(state, atomStream) + atomsIn := walk.Atomise(in) + atomsOut, error := subex.RunTransducer(state, atomsIn) if error { return nil, true } - valuesOut, err := walk.MemoryCompound(atomsOut) + valuesOut, err := walk.Compound(atomsOut) if err != nil { return nil, true } diff --git a/subex/arithmetic.go b/subex/arithmetic.go index 52f576d..a7dc73a 100644 --- a/subex/arithmetic.go +++ b/subex/arithmetic.go @@ -10,7 +10,7 @@ func sumValues(atoms []walk.Atom) ([]walk.Atom, error) { allBools := true var sum float64 = 0 var any bool = false - values, err := walk.MemoryCompound(atoms) + values, err := walk.Compound(atoms) if err != nil { return nil, err } @@ -50,7 +50,7 @@ func multiplyValues(atoms []walk.Atom) ([]walk.Atom, error) { allBools := true var product float64 = 1 var all bool = false - values, err := walk.MemoryCompound(atoms) + values, err := walk.Compound(atoms) if err != nil { return nil, err } @@ -89,7 +89,7 @@ func multiplyValues(atoms []walk.Atom) ([]walk.Atom, error) { // Does tries to cast all to numbers and negates them func negateValues(atoms []walk.Atom) ([]walk.Atom, error) { var negatedNumbers []walk.Atom - values, err := walk.MemoryCompound(atoms) + values, err := walk.Compound(atoms) if err != nil { return nil, err } @@ -123,7 +123,7 @@ func negateValues(atoms []walk.Atom) ([]walk.Atom, error) { // Else errors func reciprocalValues(atoms []walk.Atom) ([]walk.Atom, error) { var reciprocals []walk.Atom - values, err := walk.MemoryCompound(atoms) + values, err := walk.Compound(atoms) if err != nil { return nil, err } @@ -156,7 +156,7 @@ func reciprocalValues(atoms []walk.Atom) ([]walk.Atom, error) { // If all are castable to booleans, NOTs all and returns them // Else errors func notValues(atoms []walk.Atom) (notted []walk.Atom, err error) { - values, err := walk.MemoryCompound(atoms) + values, err := walk.Compound(atoms) if err != nil { return nil, err } diff --git a/subex/main.go b/subex/main.go index 9824f10..bb688e9 100644 --- a/subex/main.go +++ b/subex/main.go @@ -103,13 +103,13 @@ func pruneStates(states []SubexBranch) (newStates []SubexBranch) { } // Run the subex transducer -func RunTransducer(transducer SubexState, input <-chan walk.Atom) (output []walk.Atom, err bool) { +func RunTransducer(transducer SubexState, input []walk.Atom) (output []walk.Atom, err bool) { states := []SubexBranch{{ state: transducer, outputStack: OutputStackNil{}.push(nil), store: make(Store), }} - for piece := range input { + for _, piece := range input { var newStates []SubexBranch for _, state := range states { newStates = append(newStates, state.eat(piece)...) @@ -149,7 +149,12 @@ func Main() { close(out) }(jsonStream, tokenStream) - atoms := walk.Atomise(tokenStream) + var tokens []walk.WalkValue + for token := range tokenStream { + tokens = append(tokens, token) + } + + atoms := walk.Atomise(tokens) output, err := RunTransducer(transducer, atoms) if err { @@ -157,7 +162,7 @@ func Main() { return } - valueOut, error := walk.MemoryCompound(output) + valueOut, error := walk.Compound(output) if error != nil { fmt.Println(error.Error()) return diff --git a/walk/walk.go b/walk/walk.go index 5c1ca75..48aff34 100644 --- a/walk/walk.go +++ b/walk/walk.go @@ -48,8 +48,8 @@ const ( MapBegin MapEnd ) -func (value TerminalValue) Pieces(out chan<- Atom) { - out<-value +func (value TerminalValue) Atomise() []Atom { + return []Atom{value} } func (value TerminalValue) String() string { switch value { @@ -68,8 +68,8 @@ func (value TerminalValue) String() string { func (value TerminalValue) atomness() {} type ValueNull struct {} -func (value ValueNull) Pieces(out chan<- Atom) { - out<-value +func (value ValueNull) Atomise() []Atom { + return []Atom{ValueNull{}} } func (value ValueNull) String() string { return "null" @@ -77,8 +77,8 @@ func (value ValueNull) String() string { func (value ValueNull) atomness() {} type ValueBool bool -func (value ValueBool) Pieces(out chan<- Atom) { - out<-value +func (value ValueBool) Atomise() []Atom { + return []Atom{value} } func (value ValueBool) String() string { if value { @@ -90,8 +90,8 @@ func (value ValueBool) String() string { func (value ValueBool) atomness() {} type ValueNumber float64 -func (value ValueNumber) Pieces(out chan<- Atom) { - out<-value +func (value ValueNumber) Atomise() []Atom { + return []Atom{value} } func (value ValueNumber) String() string { v := float64(value) @@ -106,12 +106,13 @@ type StringAtom rune func (value StringAtom) atomness() {} type ValueString string -func (value ValueString) Pieces(out chan<- Atom) { - out<-StringTerminal{} +func (value ValueString) Atomise() (out []Atom) { + out = append(out, StringTerminal{}) for _, char := range value { - out<-StringAtom(char) + out = append(out, StringAtom(char)) } - out<-StringTerminal{} + out = append(out, StringTerminal{}) + return out } func (value ValueString) String() string { return fmt.Sprintf("\"%s\"", string(value)) @@ -123,7 +124,7 @@ type Atom interface { } type WalkValue interface { - Pieces(out chan<- Atom) + Atomise() []Atom String() string } @@ -423,28 +424,9 @@ func ConcatData(first []Atom, second []Atom) []Atom { return append(append([]Atom(nil), first...), second...) } -func Atomise(in <-chan WalkValue) <-chan Atom { - out := make(chan Atom) - go func(out chan<- Atom, input <-chan WalkValue) { - for value := range input { - value.Pieces(out) - } - close(out) - }(out, in) - return out -} - -func MemoryAtomise(in []WalkValue) (out []Atom) { - inChan := make(chan WalkValue) - go func(in []WalkValue, out chan<- WalkValue) { - for _, value := range in { - out<-value - } - close(out) - }(in, inChan) - outChan := Atomise(inChan) - for atom := range outChan { - out = append(out, atom) +func Atomise(in []WalkValue) (out []Atom) { + for _, value := range in { + out = append(out, value.Atomise()...) } return out } @@ -478,82 +460,59 @@ type CompoundResult struct { error error } -func Compound(in <-chan Atom) <-chan CompoundResult { - out := make(chan CompoundResult) - go func(out chan<- CompoundResult, in <-chan Atom) { - outer: for { - atom, hasAtom := <-in - if !hasAtom { - break +func Compound(in []Atom) (out []WalkValue, error error) { + i := 0 + for { + if i >= len(in) { + break + } + atom := in[i] + i++ + switch v := atom.(type) { + case TerminalValue: + out = append(out, v) + continue + case ValueNull: + out = append(out, v) + continue + case ValueBool: + out = append(out, v) + continue + case ValueNumber: + out = append(out, v) + continue + case StringAtom: + return nil, CompoundRuneOutsideString + case StringTerminal: + default: + return nil, CompoundUnknownAtom + } + // Handle string start + var builder strings.Builder + loop: for { + if i >= len(in) { + return nil, CompoundMissingEnd } + atom := in[i] + i++ switch v := atom.(type) { - case TerminalValue: - out<-CompoundResult{v, nil} - continue + case StringTerminal: + break loop + case StringAtom: + builder.WriteRune(rune(v)) case ValueNull: - out<-CompoundResult{v, nil} - continue + builder.WriteString(v.String()) case ValueBool: - out<-CompoundResult{v, nil} - continue + builder.WriteString(v.String()) case ValueNumber: - out<-CompoundResult{v, nil} - continue - case StringAtom: - out<-CompoundResult{nil, CompoundRuneOutsideString} - break outer - case StringTerminal: + builder.WriteString(v.String()) + case TerminalValue: + builder.WriteString(v.String()) default: - out<-CompoundResult{nil, CompoundUnknownAtom} - break outer - } - // Handle string start - var builder strings.Builder - loop: for { - atom, hasAtom := <-in - if !hasAtom { - out<-CompoundResult{nil, CompoundMissingEnd} - break outer - } - switch v := atom.(type) { - case StringTerminal: - break loop - case StringAtom: - builder.WriteRune(rune(v)) - case ValueNull: - builder.WriteString(v.String()) - case ValueBool: - builder.WriteString(v.String()) - case ValueNumber: - builder.WriteString(v.String()) - case TerminalValue: - builder.WriteString(v.String()) - default: - out<-CompoundResult{nil, CompoundInvalidStringAtom} - break outer - } + return nil, CompoundInvalidStringAtom } - out<-CompoundResult{ValueString(builder.String()), nil} } - close(out) - }(out, in) - return out -} - -func MemoryCompound(in []Atom) (out []WalkValue, err error) { - inChan := make(chan Atom) - go func(in []Atom, out chan<- Atom) { - for _, atom := range in { - out<-atom - } - close(out) - }(in, inChan) - outChan := Compound(inChan) - for result := range outChan { - if result.error != nil { - return out, result.error - } - out = append(out, result.value) + out = append(out, ValueString(builder.String())) } return out, nil -} \ No newline at end of file +} -- cgit v1.2.3