Optimization: use memchr for searching a byte inside bytes

crystal-lang · Nov 20, 2016 · 44bc1dd · 44bc1dd
1 parent 584060e
commit 44bc1dd
Showing 12 changed files with 55 additions and 0 deletions.
diff --git a/src/array.cr b/src/array.cr
@@ -1940,6 +1940,17 @@ class Array(T)
     {from, size}
   end
 
+  # :nodoc:
+  def index(object, offset : Int = 0)
+    # Optimize for the case of looking for a byte in a byte slice
+    if T.is_a?(UInt8.class) &&
+       (object.is_a?(UInt8) || (object.is_a?(Int) && 0 <= object < 256))
+      return Slice.new(to_unsafe, size).fast_index(object, offset)
+    end
+
+    super
+  end
+
   private class PermutationIterator(T)
     include Iterator(Array(T))
 

diff --git a/src/lib_c/aarch64-linux-gnu/c/string.cr b/src/lib_c/aarch64-linux-gnu/c/string.cr
@@ -1,6 +1,7 @@
 require "./stddef"
 
 lib LibC
+  fun memchr(x0 : Void*, c : Int, n : SizeT) : Void*
   fun memcmp(s1 : Void*, s2 : Void*, n : SizeT) : Int
   fun strcmp(s1 : Char*, s2 : Char*) : Int
   fun strerror(errnum : Int) : Char*

diff --git a/src/lib_c/amd64-unknown-openbsd/c/string.cr b/src/lib_c/amd64-unknown-openbsd/c/string.cr
@@ -1,6 +1,7 @@
 require "./stddef"
 
 lib LibC
+  fun memchr(x0 : Void*, c : Int, n : SizeT) : Void*
   fun memcmp(x0 : Void*, x1 : Void*, x2 : SizeT) : Int
   fun strcmp(x0 : Char*, x1 : Char*) : Int
   fun strerror(x0 : Int) : Char*

diff --git a/src/lib_c/arm-linux-gnueabihf/c/string.cr b/src/lib_c/arm-linux-gnueabihf/c/string.cr
@@ -1,6 +1,7 @@
 require "./stddef"
 
 lib LibC
+  fun memchr(x0 : Void*, c : Int, n : SizeT) : Void*
   fun memcmp(s1 : Void*, s2 : Void*, n : SizeT) : Int
   fun strcmp(s1 : Char*, s2 : Char*) : Int
   fun strerror(errnum : Int) : Char*

diff --git a/src/lib_c/i686-linux-gnu/c/string.cr b/src/lib_c/i686-linux-gnu/c/string.cr
@@ -1,6 +1,7 @@
 require "./stddef"
 
 lib LibC
+  fun memchr(x0 : Void*, c : Int, n : SizeT) : Void*
   fun memcmp(s1 : Void*, s2 : Void*, n : SizeT) : Int
   fun strcmp(s1 : Char*, s2 : Char*) : Int
   fun strerror(errnum : Int) : Char*

diff --git a/src/lib_c/i686-linux-musl/c/string.cr b/src/lib_c/i686-linux-musl/c/string.cr
@@ -1,6 +1,7 @@
 require "./stddef"
 
 lib LibC
+  fun memchr(x0 : Void*, c : Int, n : SizeT) : Void*
   fun memcmp(x0 : Void*, x1 : Void*, x2 : SizeT) : Int
   fun strcmp(x0 : Char*, x1 : Char*) : Int
   fun strerror(x0 : Int) : Char*

diff --git a/src/lib_c/x86_64-linux-gnu/c/string.cr b/src/lib_c/x86_64-linux-gnu/c/string.cr
@@ -1,6 +1,7 @@
 require "./stddef"
 
 lib LibC
+  fun memchr(x0 : Void*, c : Int, n : SizeT) : Void*
   fun memcmp(s1 : Void*, s2 : Void*, n : SizeT) : Int
   fun strcmp(s1 : Char*, s2 : Char*) : Int
   fun strerror(errnum : Int) : Char*

diff --git a/src/lib_c/x86_64-linux-musl/c/string.cr b/src/lib_c/x86_64-linux-musl/c/string.cr
@@ -1,6 +1,7 @@
 require "./stddef"
 
 lib LibC
+  fun memchr(x0 : Void*, c : Int, n : SizeT) : Void*
   fun memcmp(x0 : Void*, x1 : Void*, x2 : SizeT) : Int
   fun strcmp(x0 : Char*, x1 : Char*) : Int
   fun strerror(x0 : Int) : Char*

diff --git a/src/lib_c/x86_64-macosx-darwin/c/string.cr b/src/lib_c/x86_64-macosx-darwin/c/string.cr
@@ -1,6 +1,7 @@
 require "./stddef"
 
 lib LibC
+  fun memchr(x0 : Void*, c : Int, n : SizeT) : Void*
   fun memcmp(x0 : Void*, x1 : Void*, x2 : SizeT) : Int
   fun strcmp(x0 : Char*, x1 : Char*) : Int
   fun strerror(x0 : Int) : Char*

diff --git a/src/lib_c/x86_64-portbld-freebsd/c/string.cr b/src/lib_c/x86_64-portbld-freebsd/c/string.cr
@@ -1,6 +1,7 @@
 require "./stddef"
 
 lib LibC
+  fun memchr(x0 : Void*, c : Int, n : SizeT) : Void*
   fun memcmp(x0 : Void*, x1 : Void*, x2 : SizeT) : Int
   fun strcmp(x0 : Char*, x1 : Char*) : Int
   fun strerror(x0 : Int) : Char*

diff --git a/src/slice.cr b/src/slice.cr
@@ -415,6 +415,30 @@ struct Slice(T)
   def to_unsafe : Pointer(T)
     @pointer
   end
+
+  # :nodoc:
+  def index(object, offset : Int = 0)
+    # Optimize for the case of looking for a byte in a byte slice
+    if T.is_a?(UInt8.class) &&
+       (object.is_a?(UInt8) || (object.is_a?(Int) && 0 <= object < 256))
+      return fast_index(object, offset)
+    end
+
+    super
+  end
+
+  # :nodoc:
+  def fast_index(object, offset)
+    offset += size if offset < 0
+    if 0 <= offset < size
+      result = LibC.memchr(to_unsafe + offset, object, size - offset)
+      if result
+        return (result - to_unsafe.as(Void*)).to_i32
+      end
+    end
+
+    nil
+  end
 end
 
 alias Bytes = Slice(UInt8)
diff --git a/src/static_array.cr b/src/static_array.cr
@@ -217,4 +217,15 @@ struct StaticArray(T, N)
     end
     array
   end
+
+  # :nodoc:
+  def index(object, offset : Int = 0)
+    # Optimize for the case of looking for a byte in a byte slice
+    if T.is_a?(UInt8.class) &&
+       (object.is_a?(UInt8) || (object.is_a?(Int) && 0 <= object < 256))
+      return to_slice.fast_index(object, offset)
+    end
+
+    super
+  end
 end