Optimization/simplification of 'getbaseline'
By producing absolute line information at regular intervals, a simple
division can compute the correct entry for a given instruction.
diff --git a/lcode.c b/lcode.c
index 9741d7c..31f23f4 100644
--- a/lcode.c
+++ b/lcode.c
@@ -328,13 +328,13 @@
static void savelineinfo (FuncState *fs, Proto *f, int line) {
int linedif = line - fs->previousline;
int pc = fs->pc - 1; /* last instruction coded */
- if (abs(linedif) >= LIMLINEDIFF || fs->iwthabs++ > MAXIWTHABS) {
+ if (abs(linedif) >= LIMLINEDIFF || fs->iwthabs++ >= MAXIWTHABS) {
luaM_growvector(fs->ls->L, f->abslineinfo, fs->nabslineinfo,
f->sizeabslineinfo, AbsLineInfo, MAX_INT, "lines");
f->abslineinfo[fs->nabslineinfo].pc = pc;
f->abslineinfo[fs->nabslineinfo++].line = line;
linedif = ABSLINEINFO; /* signal that there is absolute information */
- fs->iwthabs = 0; /* restart counter */
+ fs->iwthabs = 1; /* restart counter */
}
luaM_growvector(fs->ls->L, f->lineinfo, pc, f->sizelineinfo, ls_byte,
MAX_INT, "opcodes");
diff --git a/ldebug.c b/ldebug.c
index 8dfa18c..0038d1b 100644
--- a/ldebug.c
+++ b/ldebug.c
@@ -46,10 +46,14 @@
/*
** Get a "base line" to find the line corresponding to an instruction.
-** For that, search the array of absolute line info for the largest saved
-** instruction smaller or equal to the wanted instruction. A special
-** case is when there is no absolute info or the instruction is before
-** the first absolute one.
+** Base lines are regularly placed at MAXIWTHABS intervals, so usually
+** an integer division gets the right place. When the source file has
+** large sequences of empty/comment lines, it may need extra entries,
+** so the original estimate needs a correction.
+** The assertion that the estimate is a lower bound for the correct base
+** is valid as long as the debug info has been generated with the same
+** value for MAXIWTHABS or smaller. (Previous releases use a little
+** smaller value.)
*/
static int getbaseline (const Proto *f, int pc, int *basepc) {
if (f->sizeabslineinfo == 0 || pc < f->abslineinfo[0].pc) {
@@ -57,20 +61,11 @@
return f->linedefined;
}
else {
- unsigned int i;
- if (pc >= f->abslineinfo[f->sizeabslineinfo - 1].pc)
- i = f->sizeabslineinfo - 1; /* instruction is after last saved one */
- else { /* binary search */
- unsigned int j = f->sizeabslineinfo - 1; /* pc < anchorlines[j] */
- i = 0; /* abslineinfo[i] <= pc */
- while (i < j - 1) {
- unsigned int m = (j + i) / 2;
- if (pc >= f->abslineinfo[m].pc)
- i = m;
- else
- j = m;
- }
- }
+ int i = cast_uint(pc) / MAXIWTHABS - 1; /* get an estimate */
+ /* estimate must be a lower bond of the correct base */
+ lua_assert(i < f->sizeabslineinfo && f->abslineinfo[i].pc <= pc);
+ while (i + 1 < f->sizeabslineinfo && pc >= f->abslineinfo[i + 1].pc)
+ i++; /* low estimate; adjust it */
*basepc = f->abslineinfo[i].pc;
return f->abslineinfo[i].line;
}
@@ -303,8 +298,8 @@
sethvalue2s(L, L->top, t); /* push it on stack */
api_incr_top(L);
setbtvalue(&v); /* boolean 'true' to be the value of all indices */
- for (i = 0; i < p->sizelineinfo; i++) { /* for all lines with code */
- currentline = nextline(p, currentline, i);
+ for (i = 0; i < p->sizelineinfo; i++) { /* for all instructions */
+ currentline = nextline(p, currentline, i); /* get its line */
luaH_setint(L, t, currentline, &v); /* table[line] = true */
}
}
diff --git a/ldebug.h b/ldebug.h
index 8e912a8..974960e 100644
--- a/ldebug.h
+++ b/ldebug.h
@@ -29,10 +29,10 @@
/*
** MAXimum number of successive Instructions WiTHout ABSolute line
-** information.
+** information. (A power of two allows fast divisions.)
*/
#if !defined(MAXIWTHABS)
-#define MAXIWTHABS 120
+#define MAXIWTHABS 128
#endif