Faster string sorting

6 files changed, 24 insertions, 5 deletions

diff --git a/src/install/bit_set.zig b/src/bit_set.zig
index bd6d71027..f334ae826 100644
--- a/src/install/bit_set.zig
+++ b/src/bit_set.zig
@@ -781,6 +781,12 @@ pub const DynamicBitSetUnmanaged = struct {
         return (self.masks[maskIndex(index)] & maskBit(index)) != 0;
     }
 
+    pub fn byteRange(self: Self, start: usize, len: usize) []const u8 {
+        assert(start < self.bit_length);
+        const offset = maskIndex(start);
+        return std.mem.sliceAsBytes(self.masks[offset .. offset + len]);
+    }
+
     /// Returns the total number of set bits in this bit set.
     pub fn count(self: Self) usize {
         const num_masks = (self.bit_length + (@bitSizeOf(MaskInt) - 1)) / @bitSizeOf(MaskInt);
diff --git a/src/bun.zig b/src/bun.zig
index 1cbeaaf86..a9528aa64 100644
--- a/src/bun.zig
+++ b/src/bun.zig
@@ -743,7 +743,7 @@ pub const js_printer = @import("./js_printer.zig");
 pub const js_lexer = @import("./js_lexer.zig");
 pub const JSON = @import("./json_parser.zig");
 pub const JSAst = @import("./js_ast.zig");
-pub const bit_set = @import("./install/bit_set.zig");
+pub const bit_set = @import("./bit_set.zig");
 
 pub fn enumMap(comptime T: type, comptime args: anytype) (fn (T) []const u8) {
     const Map = struct {
diff --git a/src/c.zig b/src/c.zig
index 54be0878c..57a4b6548 100644
--- a/src/c.zig
+++ b/src/c.zig
@@ -38,6 +38,8 @@ pub extern "c" fn truncate([*:0]const u8, i64) c_int; // note: truncate64 is not
 pub extern "c" fn lutimes(path: [*:0]const u8, times: *const [2]std.os.timeval) c_int;
 pub extern "c" fn mkdtemp(template: [*c]u8) ?[*:0]u8;
 
+pub extern "c" fn memcmp(s1: [*c]const u8, s2: [*c]const u8, n: usize) c_int;
+
 pub const lstat = lstat64;
 pub const fstat = fstat64;
 pub const stat = stat64;
diff --git a/src/install/lockfile.zig b/src/install/lockfile.zig
index 084ad7616..2c7f897e3 100644
--- a/src/install/lockfile.zig
+++ b/src/install/lockfile.zig
@@ -46,7 +46,7 @@ const Integrity = @import("./integrity.zig").Integrity;
 const clap = @import("bun").clap;
 const ExtractTarball = @import("./extract_tarball.zig");
 const Npm = @import("./npm.zig");
-const Bitset = @import("./bit_set.zig").DynamicBitSetUnmanaged;
+const Bitset = bun.bit_set.DynamicBitSetUnmanaged;
 const z_allocator = @import("../memory_allocator.zig").z_allocator;
 const Lockfile = @This();
 
diff --git a/src/install/semver.zig b/src/install/semver.zig
index c4d9b5b5f..1dca9df49 100644
--- a/src/install/semver.zig
+++ b/src/install/semver.zig
@@ -94,7 +94,7 @@ pub const String = extern struct {
         lhs_buf: []const u8,
         rhs_buf: []const u8,
     ) std.math.Order {
-        return std.mem.order(u8, lhs.slice(lhs_buf), rhs.slice(rhs_buf));
+        return strings.order(lhs.slice(lhs_buf), rhs.slice(rhs_buf));
     }
 
     pub inline fn canInline(buf: []const u8) bool {
diff --git a/src/string_immutable.zig b/src/string_immutable.zig
index 55e7f9225..caf09ae02 100644
--- a/src/string_immutable.zig
+++ b/src/string_immutable.zig
@@ -3783,12 +3783,23 @@ pub fn join(slices: []const string, delimiter: string, allocator: std.mem.Alloca
     return try std.mem.join(allocator, delimiter, slices);
 }
 
+pub fn order(a: []const u8, b: []const u8) std.math.Order {
+    const len = @min(a.len, b.len);
+    const cmp = bun.C.memcmp(a.ptr, b.ptr, len);
+    return switch (cmp) {
+        0 => std.math.order(a.len, b.len),
+        1 => .gt,
+        -1 => .lt,
+        else => unreachable,
+    };
+}
+
 pub fn cmpStringsAsc(_: void, a: string, b: string) bool {
-    return std.mem.order(u8, a, b) == .lt;
+    return order(a, b) == .lt;
 }
 
 pub fn cmpStringsDesc(_: void, a: string, b: string) bool {
-    return std.mem.order(u8, a, b) == .gt;
+    return order(a, b) == .gt;
 }
 
 const sort_asc = std.sort.asc(u8);