From dd02a05e082b96d76707964179921107cd43cdd8 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Sat, 2 Apr 2016 15:18:26 +0200 Subject: build system: finer-grained selection of search speedup table. KNOWN_APPNAME_OFFSETS=8 versus KNOWN_APPNAME_OFFSETS=0: function old new delta find_applet_by_name 55 136 +81 applet_nameofs - 14 +14 run_applet_and_exit 757 758 +1 Signed-off-by: Denys Vlasenko --- applets/applet_tables.c | 65 +++++++++++++++++++++++++------------------------ 1 file changed, 33 insertions(+), 32 deletions(-) (limited to 'applets') diff --git a/applets/applet_tables.c b/applets/applet_tables.c index 48544f08d..843f2ec08 100644 --- a/applets/applet_tables.c +++ b/applets/applet_tables.c @@ -58,41 +58,32 @@ static int str_isalnum_(const char *s) return 1; } -// Before linear search, narrow it down by looking at N "equidistant" names: -// KNOWN_APPNAME_OFFSETS cycles code_size -// 0 9057 -// 2 4604 +32 -// 4 2407 +75 -// 8 1342 +98 -// 16 908 +130 -// 32 884 +194 -// With 8, applet_nameofs[] table has 7 elements. -#define KNOWN_APPNAME_OFFSETS 8 - int main(int argc, char **argv) { int i, j; - int ofs, offset[KNOWN_APPNAME_OFFSETS], index[KNOWN_APPNAME_OFFSETS]; -// unsigned MAX_APPLET_NAME_LEN = 1; - qsort(applets, NUM_APPLETS, sizeof(applets[0]), cmp_name); + // In find_applet_by_name(), before linear search, narrow it down + // by looking at N "equidistant" names. With ~350 applets: + // KNOWN_APPNAME_OFFSETS cycles + // 0 9057 + // 2 4604 + ~100 bytes of code + // 4 2407 + 4 bytes + // 8 1342 + 8 bytes + // 16 908 + 16 bytes + // 32 884 + 32 bytes + // With 8, int16_t applet_nameofs[] table has 7 elements. + int KNOWN_APPNAME_OFFSETS = 8; + // With 128 applets we do two linear searches, with 1..7 strcmp's in the first one + // and 1..16 strcmp's in the second. With 256 apps, second search does 1..32 strcmp's. + if (NUM_APPLETS < 128) + KNOWN_APPNAME_OFFSETS = 4; + if (NUM_APPLETS < 32) + KNOWN_APPNAME_OFFSETS = 0; - for (i = 0; i < KNOWN_APPNAME_OFFSETS; i++) - index[i] = i * NUM_APPLETS / KNOWN_APPNAME_OFFSETS; + qsort(applets, NUM_APPLETS, sizeof(applets[0]), cmp_name); - ofs = 0; - for (i = 0; i < NUM_APPLETS; i++) { - for (j = 0; j < KNOWN_APPNAME_OFFSETS; j++) - if (i == index[j]) - offset[j] = ofs; - ofs += strlen(applets[i].name) + 1; - } - /* If the list of names is too long refuse to proceed */ - if (ofs > 0xffff) - return 1; if (!argv[1]) return 1; - i = open(argv[1], O_WRONLY | O_TRUNC | O_CREAT, 0666); if (i < 0) return 1; @@ -108,16 +99,26 @@ int main(int argc, char **argv) printf("#define SINGLE_APPLET_MAIN %s_main\n", applets[0].main); } - if (KNOWN_APPNAME_OFFSETS > 0 && NUM_APPLETS > 2*KNOWN_APPNAME_OFFSETS) { - printf("#define KNOWN_APPNAME_OFFSETS %u\n\n", KNOWN_APPNAME_OFFSETS); + printf("#define KNOWN_APPNAME_OFFSETS %u\n\n", KNOWN_APPNAME_OFFSETS); + if (KNOWN_APPNAME_OFFSETS > 0) { + int ofs, offset[KNOWN_APPNAME_OFFSETS], index[KNOWN_APPNAME_OFFSETS]; + for (i = 0; i < KNOWN_APPNAME_OFFSETS; i++) + index[i] = i * NUM_APPLETS / KNOWN_APPNAME_OFFSETS; + ofs = 0; + for (i = 0; i < NUM_APPLETS; i++) { + for (j = 0; j < KNOWN_APPNAME_OFFSETS; j++) + if (i == index[j]) + offset[j] = ofs; + ofs += strlen(applets[i].name) + 1; + } + /* If the list of names is too long refuse to proceed */ + if (ofs > 0xffff) + return 1; printf("const uint16_t applet_nameofs[] ALIGN2 = {\n"); for (i = 1; i < KNOWN_APPNAME_OFFSETS; i++) printf("%d,\n", offset[i]); printf("};\n\n"); } - else { - printf("#define KNOWN_APPNAME_OFFSETS 0\n\n"); - } //printf("#ifndef SKIP_definitions\n"); printf("const char applet_names[] ALIGN1 = \"\"\n"); -- cgit v1.2.3