commit 42cdf5839f7c52fe506cb1a3d459f7609c8c4ef8
parent 5bb76983d44810cd47de7b80b17347162ecd5e10
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Tue, 16 Jun 2026 11:06:28 -0700
Speed up ar replacement indexing
Diffstat:
4 files changed, 188 insertions(+), 8 deletions(-)
diff --git a/driver/cmd/ar.c b/driver/cmd/ar.c
@@ -142,6 +142,134 @@ static void ar_set_input_member(KitArInput* out, const char* name,
out->bytes.len = fd->size;
}
+typedef struct ArNameSlot {
+ const char* name;
+ size_t len;
+ uint32_t head_plus_one;
+ uint32_t tail_plus_one;
+ uint32_t hash;
+} ArNameSlot;
+
+typedef struct ArNameIndex {
+ DriverEnv* env;
+ ArNameSlot* slots;
+ uint32_t* next_plus_one;
+ size_t cap;
+ size_t next_cap;
+} ArNameIndex;
+
+static void ar_name_index_fini(ArNameIndex* idx);
+
+static uint32_t ar_name_hash(const char* s, size_t len) {
+ uint32_t h = 2166136261u;
+ size_t i;
+ for (i = 0; i < len; ++i) {
+ h ^= (uint8_t)s[i];
+ h *= 16777619u;
+ }
+ return h ? h : 1u;
+}
+
+static int ar_name_eq(const ArNameSlot* slot, const char* name, size_t len,
+ uint32_t hash) {
+ size_t i;
+ if (!slot->name || slot->hash != hash || slot->len != len) return 0;
+ for (i = 0; i < len; ++i)
+ if (slot->name[i] != name[i]) return 0;
+ return 1;
+}
+
+static int ar_name_index_init(ArNameIndex* idx, DriverEnv* env,
+ size_t max_entries) {
+ size_t cap = 16;
+ idx->env = env;
+ idx->slots = NULL;
+ idx->next_plus_one = NULL;
+ idx->cap = 0;
+ idx->next_cap = 0;
+ if (max_entries == 0) return 1;
+ while (cap < max_entries * 2u) cap *= 2u;
+ idx->slots = (ArNameSlot*)driver_alloc_zeroed(env, cap * sizeof(*idx->slots));
+ idx->next_plus_one =
+ (uint32_t*)driver_alloc_zeroed(env, max_entries * sizeof(*idx->next_plus_one));
+ if (!idx->slots || !idx->next_plus_one) {
+ ar_name_index_fini(idx);
+ return 0;
+ }
+ idx->cap = cap;
+ idx->next_cap = max_entries;
+ return 1;
+}
+
+static void ar_name_index_fini(ArNameIndex* idx) {
+ if (idx->slots)
+ driver_free(idx->env, idx->slots, idx->cap * sizeof(*idx->slots));
+ if (idx->next_plus_one)
+ driver_free(idx->env, idx->next_plus_one,
+ idx->next_cap * sizeof(*idx->next_plus_one));
+ idx->env = NULL;
+ idx->slots = NULL;
+ idx->next_plus_one = NULL;
+ idx->cap = 0;
+ idx->next_cap = 0;
+}
+
+static int ar_name_index_take(ArNameIndex* idx, const char* name, size_t len,
+ uint32_t* out_index) {
+ uint32_t hash;
+ size_t mask;
+ size_t pos;
+ if (!idx->slots) return 0;
+ hash = ar_name_hash(name, len);
+ mask = idx->cap - 1u;
+ pos = hash & mask;
+ for (;;) {
+ const ArNameSlot* slot = &idx->slots[pos];
+ if (!slot->name) return 0;
+ if (ar_name_eq(slot, name, len, hash)) {
+ ArNameSlot* mut = &idx->slots[pos];
+ uint32_t index;
+ if (!mut->head_plus_one) return 0;
+ index = mut->head_plus_one - 1u;
+ mut->head_plus_one = idx->next_plus_one[index];
+ if (!mut->head_plus_one) mut->tail_plus_one = 0;
+ *out_index = index;
+ return 1;
+ }
+ pos = (pos + 1u) & mask;
+ }
+}
+
+static void ar_name_index_insert_old(ArNameIndex* idx, const char* name,
+ size_t len, uint32_t member_index) {
+ uint32_t hash = ar_name_hash(name, len);
+ size_t mask = idx->cap - 1u;
+ size_t pos = hash & mask;
+ if (member_index >= idx->next_cap) return;
+ for (;;) {
+ ArNameSlot* slot = &idx->slots[pos];
+ if (!slot->name) {
+ slot->name = name;
+ slot->len = len;
+ slot->hash = hash;
+ slot->head_plus_one = member_index + 1u;
+ slot->tail_plus_one = member_index + 1u;
+ return;
+ }
+ if (ar_name_eq(slot, name, len, hash)) {
+ if (slot->tail_plus_one) {
+ idx->next_plus_one[slot->tail_plus_one - 1u] = member_index + 1u;
+ slot->tail_plus_one = member_index + 1u;
+ } else {
+ slot->head_plus_one = member_index + 1u;
+ slot->tail_plus_one = member_index + 1u;
+ }
+ return;
+ }
+ pos = (pos + 1u) & mask;
+ }
+}
+
/* Open the archive bytes via file_io. Caller releases fd via ctx. */
static int ar_open_for_read(DriverEnv* env, const char* path,
KitContext* ctx_out, KitFileData* fd_out,
@@ -327,6 +455,7 @@ static int ar_do_write(DriverEnv* env, const char* archive_path, int nmembers,
* via kit_obj_global_syms_free which recovers the size from the block. */
KitArMemberSymbols* msyms = NULL;
void** sym_allocs = NULL;
+ ArNameIndex name_index = {0};
opts.epoch = driver_epoch_from_env();
opts.long_names = 1;
@@ -408,6 +537,16 @@ static int ar_do_write(DriverEnv* env, const char* archive_path, int nmembers,
}
kit_ar_iter_free(it);
}
+ if (nm > 0) {
+ if (!ar_name_index_init(&name_index, env, nm)) {
+ driver_errf(AR_TOOL, "out of memory");
+ rc = 1;
+ goto done;
+ }
+ for (i = 0; i < nm; ++i)
+ ar_name_index_insert_old(&name_index, members[i].name.s,
+ members[i].name.len, i);
+ }
} else {
/* `c`: overwrite. */
members_cap = (size_t)nnew;
@@ -433,6 +572,7 @@ static int ar_do_write(DriverEnv* env, const char* archive_path, int nmembers,
for (i = 0; i < nnew; ++i) {
const char* path = member_paths[i];
const char* base = driver_basename(path);
+ size_t base_len = driver_strlen(base);
if (ctx.file_io->read_all(ctx.file_io->user, path, &new_fds[i]) !=
KIT_OK) {
driver_errf(AR_TOOL, "failed to read: %.*s",
@@ -443,17 +583,20 @@ static int ar_do_write(DriverEnv* env, const char* archive_path, int nmembers,
if (has_r) {
/* Replace existing slot if a member with the same basename
* is already present; otherwise append. */
- uint32_t j;
+ uint32_t j = 0;
int replaced = 0;
- for (j = 0; j < nm; ++j) {
- if (driver_streq(members[j].name.s, base)) {
- ar_set_input_member(&members[j], base, &new_fds[i]);
- replaced = 1;
- break;
- }
+ if (ar_name_index_take(&name_index, base, base_len, &j)) {
+ members[j].name.s = base;
+ members[j].name.len = base_len;
+ members[j].bytes.data = new_fds[i].data;
+ members[j].bytes.len = new_fds[i].size;
+ replaced = 1;
}
if (!replaced) {
- ar_set_input_member(&members[nm], base, &new_fds[i]);
+ members[nm].name.s = base;
+ members[nm].name.len = base_len;
+ members[nm].bytes.data = new_fds[i].data;
+ members[nm].bytes.len = new_fds[i].size;
nm++;
}
if (has_v)
@@ -504,6 +647,7 @@ static int ar_do_write(DriverEnv* env, const char* archive_path, int nmembers,
}
done:
+ ar_name_index_fini(&name_index);
if (sym_allocs) {
for (i = 0; i < nm; ++i) {
if (sym_allocs[i]) kit_obj_global_syms_free(&ctx, sym_allocs[i]);
diff --git a/scripts/ecosystem_speed.sh b/scripts/ecosystem_speed.sh
@@ -26,12 +26,18 @@ RUNS="${ECO_SPEED_RUNS:-${RUNS:-5}}"
TIMEOUT_S="${ECO_SPEED_TIMEOUT:-${TIMEOUT:-20}}"
OPTS="${ECO_SPEED_OPTS:-O0 O1}"
OUT_ROOT="${ECO_SPEED_OUT:-$ROOT/build/ecosystem-speed}"
+QUIET="${ECO_SPEED_QUIET:-0}"
die() {
printf 'ecosystem-speed: %s\n' "$*" >&2
exit 2
}
+progress() {
+ [ "$QUIET" = 1 ] && return 0
+ printf 'ecosystem-speed: %s\n' "$*" >&2
+}
+
usage() {
cat <<EOF
usage: scripts/ecosystem_speed.sh [project ...]
@@ -46,6 +52,7 @@ env:
ECO_SPEED_OPTS opt levels, e.g. "O0 O1" (default: "O0 O1")
ECO_SPEED_PROJECTS project list if no argv is passed
ECO_SPEED_OUT output dir for logs/results (default: build/ecosystem-speed)
+ ECO_SPEED_QUIET set to 1 to suppress progress lines
EOF
}
@@ -389,6 +396,7 @@ record_best() {
local best_rc=125
local run
for run in $(seq 1 "$RUNS"); do
+ progress "$project $opt $phase $tool run $run/$RUNS"
local run_dir="$row_dir/$phase-$tool-$run"
local got rc elapsed
got=$(timed_phase "$phase" "$tool" "$run_dir" "$@")
@@ -707,6 +715,7 @@ main() {
mkdir -p "$row_dir"
local kit_compile clang_compile tcc_compile
+ progress "$project $opt compile"
kit_compile=$(best_compile_ms_for kit "$project" "$opt" "$src_list" "$sdk" "$row_dir")
clang_compile=$(best_compile_ms_for clang "$project" "$opt" "$src_list" "$sdk" "$row_dir")
tcc_compile=$(best_compile_ms_for tcc "$project" "$opt" "$src_list" "$sdk" "$row_dir")
@@ -716,17 +725,20 @@ main() {
local kit_fixture="$row_dir/fixture-kit"
local clang_fixture="$row_dir/fixture-clang"
local tcc_fixture="$row_dir/fixture-tcc"
+ progress "$project $opt fixtures"
make_fixture kit "$project" "$opt" "$src_list" "$sdk" "$kit_fixture" || true
make_fixture clang "$project" "$opt" "$src_list" "$sdk" "$clang_fixture" || true
make_fixture tcc "$project" "$opt" "$src_list" "$sdk" "$tcc_fixture" || true
local kit_ar host_ar
+ progress "$project $opt archive"
kit_ar=$(best_archive_ms_for kit "$project" "$opt" "$kit_fixture" "$row_dir")
host_ar=$(best_archive_ms_for host "$project" "$opt" "$kit_fixture" "$row_dir")
printf 'archive,%s,%s,%s,%s,,,%s\n' "$project" "$opt" "$lib_objs" \
"$kit_ar" "$host_ar" >> "$results"
local kit_link clang_link tcc_link
+ progress "$project $opt link"
kit_link=$(best_link_ms_for kit "$project" "$opt" "$kit_fixture" "$sdk" "$row_dir")
clang_link=$(best_link_ms_for clang "$project" "$opt" "$clang_fixture" "$sdk" "$row_dir")
tcc_link=$(best_link_ms_for tcc "$project" "$opt" "$tcc_fixture" "$sdk" "$row_dir")
diff --git a/test/ar/cases/07-replace-duplicate-inputs.expected b/test/ar/cases/07-replace-duplicate-inputs.expected
@@ -0,0 +1,8 @@
+== fresh duplicate rcs ==
+4 a.o
+6 a.o
+r - a.o
+r - a.o
+== replace duplicate rvs ==
+2 a.o
+3 a.o
diff --git a/test/ar/cases/07-replace-duplicate-inputs.sh b/test/ar/cases/07-replace-duplicate-inputs.sh
@@ -0,0 +1,16 @@
+# Match llvm-ar duplicate basename behavior: `r` replaces existing matching
+# members in order, then appends duplicate inputs once old matches are exhausted.
+
+mkdir one two
+printf 'aaaa' > one/a.o
+printf 'bbbbbb' > two/a.o
+
+"$KIT" ar rcs lib.a one/a.o two/a.o
+echo "== fresh duplicate rcs =="
+"$KIT" ar tv lib.a
+
+printf 'AA' > one/a.o
+printf 'BBB' > two/a.o
+"$KIT" ar rvs lib.a one/a.o two/a.o
+echo "== replace duplicate rvs =="
+"$KIT" ar tv lib.a
