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>

1 files changed, 33 insertions, 32 deletions

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");