Minor performance improvements
Change-Id: I6552b7dc082b97c28bc889a378208d0588da755b
diff --git a/Changes b/Changes
index 245f122..dd48d28 100644
--- a/Changes
+++ b/Changes
@@ -1,7 +1,8 @@
-0.2.0 2023-09-05
+0.2.1 2023-09-05
- Add english tokenizer.
- Fix buffer bug.
- Improve Readme.
+ - Minor performance improvements.
0.1.7 2023-02-28
- Add dependabot checks.
diff --git a/datok.go b/datok.go
index 88975ea..fba655e 100644
--- a/datok.go
+++ b/datok.go
@@ -113,6 +113,7 @@
var atrans *edge
var s, s1 int
var t, t1 uint32
+ var diff int
// Create a mapping from s (in Ms aka Intermediate FSA)
// to t (in Mt aka Double Array FSA)
@@ -215,9 +216,10 @@
// Store a final transition
dat.array[base+uint32(dat.final)].setCheck(t)
- if dat.maxSize < int(base)+dat.final {
- dat.maxSize = int(base) + dat.final
- }
+ // Find max
+ // see https://dev.to/jobinrjohnson/branchless-programming-does-it-really-matter-20j4
+ diff = dat.maxSize - (int(base) + dat.final)
+ dat.maxSize -= (diff & (diff >> 31))
}
}
}
@@ -461,6 +463,8 @@
dat.transCount = 0
for x := 1; x < len(dat.array); x++ {
+
+ // Hopefully branchless
if dat.array[x].getBase() != 0 {
dat.transCount++
}
@@ -512,9 +516,12 @@
max := 0
for sym, num := range dat.sigma {
sigmalist[num] = sym
- if num > max {
- max = num
- }
+
+ // Find max
+ max -= ((max - num) & ((max - num) >> 31))
+ // if num > max {
+ // max = num
+ // }
}
sigmalist = sigmalist[:max+1]
@@ -852,9 +859,7 @@
// Better not repeatedly check for a!
// Possibly keep a buffer with a.
if int(char) < 256 {
- if int(char) == EOT {
- eot = true
- }
+ eot = int(char) == EOT
a = dat.sigmaASCII[int(char)]
} else {
a, ok = dat.sigma[char]
@@ -933,6 +938,7 @@
// token and start blank at the root node of the automaton for the remaining data.
// It may be beneficial to have something like a "drop()" event to capture these cases,
// as they are likely the result of a bad automaton design.
+ // Hopefully this is branchless code
if buffc-bufft <= 0 {
buffc++
if buffc == 0 {
@@ -953,9 +959,7 @@
log.Println("-> Rewind buffer", bufft, buffc, buffi, epsilonOffset)
}
- for x, i := range buffer[buffc:buffi] {
- buffer[x] = i
- }
+ copy(buffer[0:], buffer[buffc:buffi])
buffi -= buffc
epsilonState = 0
@@ -986,6 +990,7 @@
buffc++
// Transition does not produce a character
+ // Hopefully this is branchless
if buffc-bufft == 1 && ta.isNonToken() {
if DEBUG {
log.Println("Nontoken forward", showBufferNew(buffer, bufft, buffc, buffi))
@@ -1028,10 +1033,7 @@
}
// TODO: Better as a ring buffer
- // buffer = buffer[buffc:] !slower
- for x, i := range buffer[buffc:buffi] {
- buffer[x] = i
- }
+ copy(buffer[0:], buffer[buffc:buffi])
buffi -= buffc
// epsilonOffset -= buffo
diff --git a/matrix.go b/matrix.go
index eb88086..e2d9858 100644
--- a/matrix.go
+++ b/matrix.go
@@ -55,9 +55,13 @@
if num > auto.sigmaCount {
panic("sigmaCount is smaller")
}
- if num > max {
- max = num
- }
+
+ // Find max
+ // see https://dev.to/jobinrjohnson/branchless-programming-does-it-really-matter-20j4
+ max -= ((max - num) & ((max - num) >> 31))
+ // if num > max {
+ // max = num
+ // }
}
// Add final entry to the list (maybe not necessary actually)
@@ -137,9 +141,13 @@
max := 0
for sym, num := range mat.sigma {
sigmalist[num] = sym
- if num > max {
- max = num
- }
+
+ // Find max
+ // see https://dev.to/jobinrjohnson/branchless-programming-does-it-really-matter-20j4
+ max -= ((max - num) & ((max - num) >> 31))
+ // if num > max {
+ // max = num
+ // }
}
// Add final entry to the list (maybe not necessary actually)
@@ -411,9 +419,7 @@
// Better not repeatedly check for a!
// Possibly keep a buffer with a.
if int(char) < 256 {
- if int(char) == EOT {
- eot = true
- }
+ eot = int(char) == EOT
// mat.SigmaASCII[] is initialized with mat.identity
a = mat.sigmaASCII[int(char)]
@@ -513,6 +519,7 @@
break
}
}
+ // This will hopefully be branchless by the compiler
if DEBUG {
log.Println("-> Flush buffer: [", string(buffer[bufft:buffc]), "]", showBufferNew(buffer, bufft, buffc, buffi))
@@ -527,9 +534,7 @@
log.Println("-> Rewind buffer", bufft, buffc, buffi, epsilonOffset)
}
- for x, i := range buffer[buffc:buffi] {
- buffer[x] = i
- }
+ copy(buffer[0:], buffer[buffc:buffi])
buffi -= buffc
epsilonState = 0
@@ -575,6 +580,7 @@
buffc++
// Transition does not produce a character
+ // Hopefully generated branchless code
if buffc-bufft == 1 && (t&FIRSTBIT) != 0 {
if DEBUG {
log.Println("Nontoken forward", showBufferNew(buffer, bufft, buffc, buffi))
@@ -601,10 +607,7 @@
log.Println("-> Rewind buffer", bufft, buffc, buffi, epsilonOffset)
}
- // buffer = buffer[buffc:]
- for x, i := range buffer[buffc:buffi] {
- buffer[x] = i
- }
+ copy(buffer[0:], buffer[buffc:buffi])
buffi -= buffc
// epsilonOffset -= buffo