summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDenys Vlasenko2016-04-02 15:18:26 +0200
committerDenys Vlasenko2016-04-02 15:18:26 +0200
commitdd02a05e082b96d76707964179921107cd43cdd8 (patch)
treef698e072011a48f335b8fa30babdc8724bdee011
parent9f2f96edfa7eddd8a77b76ccae7c2ed88348182e (diff)
downloadbusybox-dd02a05e082b96d76707964179921107cd43cdd8.zip
busybox-dd02a05e082b96d76707964179921107cd43cdd8.tar.gz
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 <vda.linux@googlemail.com>
-rw-r--r--applets/applet_tables.c65
1 files changed, 33 insertions, 32 deletions
diff --git a/applets/applet_tables.c b/applets/applet_tables.c
index 48544f0..843f2ec 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");