Faster/more performant way to check if strings contains a char

[rcsaquino]

I was doing some time sensitive string processing when I noticed a bottleneck on my for loop, specifically strings.contains_rune(). I experimented a little to find a way to speed up my code and found a solution (inspired by a solution on another language).

I'd like to propose a faster alternative to strings.contains_rune(). Instead of checking each characters as rune, we can check them as u8, thus it can be called contains_u8().

Here's the proposed implementation of contains_u8():

contains_u8 :: proc(s: string, c: u8) -> bool {
	for i := 0; i < len(s); i += 1 {
		if s[i] == c {
			return true
		}
	}
	return false
}

I tested the performance of contains_rune() vs contains_u8() and the latter is 2.4x faster in my testing. Here's the code I used to test:

package main

import "core:fmt"
import "core:math/rand"
import "core:strings"
import "core:time"


main :: proc() {
	sentence := "This is a sentence."
	test_length := 100_000_000
	counter := 0

	letters_u8 := []u8{'a', 'b', 'c', 'd', 'e'}
	letters_rune := []rune{'a', 'b', 'c', 'd', 'e'}

	sw: time.Stopwatch

	// Test built-in strings.contains_rune()
	time.stopwatch_start(&sw)
	for _ in 0 ..< test_length {
		i := rand.float32_range(0, 5)
		if strings.contains_rune(sentence, letters_rune[int(i)]) {
			counter += 1
		}
	}
	fmt.println("contains_rune:", time.stopwatch_duration(sw)) // `odin build . -o:speed` -> 2.7093976s
	// End

	time.stopwatch_reset(&sw)
	counter = 0

	// contains_u8 implementation
	time.stopwatch_start(&sw)
	for _ in 0 ..< test_length {
		i := rand.float32_range(0, 5)
		if contains_u8(sentence, letters_u8[int(i)]) {
			counter += 1
		}
	}
	fmt.println("contains_u8:", time.stopwatch_duration(sw)) // `odin build . -o:speed` -> 1.1135038s
	// End

	fmt.println("Debug counter:", counter)
}

contains_u8 :: proc(s: string, c: u8) -> bool {
	for i := 0; i < len(s); i += 1 {
		if s[i] == c {
			return true
		}
	}
	return false
}

I can send a pull request as soon as I get the permission.

Thanks

[Feoramund]

Both package strings and bytes already have index_byte procs which are equivalent to the one you posted.

[rcsaquino]

Whoops. Didn't see that one. Although a bit different since it returns int instead of bool but can achieve the same purpose with if x != -1.

[JesseRMeyer]

No reason to pay bounds checking costs.

  contains_u8 :: proc(str: string, c: u8) -> bool {
  	for s in str {
  		if u8(s) == c {
  			return true
  		}
  	}
  	return false
  }

[rcsaquino]

This seems to be slower than my version. I think casting the rune to u8 is more expensive than the bounds checking cost.

[JesseRMeyer]

Hard to see why that would be. What optimization mode did you build with?

[Feoramund]

for s in str will still iterate by rune, which is the slow thing here. An indexed for loop i := 0; i < len(s); i += 1 can be preceded by #no_bounds_check to disable the cost of bounds checking, or you could disable it program-wide with the -no-bounds-check compile-time flag.