[Python-ideas] Python-ideas Digest, Vol 90, Issue 30

[Nathaniel Smith]

On Thu, May 22, 2014 at 9:17 PM, Ned Batchelder <ned at nedbatchelder.com> wrote:
> On 5/22/14 1:16 PM, Nathaniel Smith wrote:
>>
>> On Thu, May 22, 2014 at 4:32 PM, Ned Batchelder <ned at nedbatchelder.com>
>> wrote:
>>>
>>> On 5/22/14 9:49 AM, Skip Montanaro wrote:
>>>>
>>>> It seems to me that Ned has revealed a bug in the peephole optimizer.
>>>> It zapped an entire source line's worth of bytecode, but failed to
>>>> delete the relevant entry in the line number table of the resulting
>>>> code object. If I had my druthers, that would be the change I'd
>>>> prefer.
>>>
>>> I think it is the nature of optimization that it will destroy useful
>>> information.  I don't think it will always be possible to retain enough
>>> back-mapping that the optimized code can be understood as if it had not
>>> been
>>> optimized.   For example, the debug issue would still be present: if you
>>> run
>>> pdb and set a breakpoint on the "continue" line, it will never be hit.
>>> Even
>>> if the optimizer cleaned up after itself perfectly (in fact, especially
>>> so),
>>> that breakpoint will still not be hit.  You simply cannot reason about
>>> optimized code without having to mentally understand the transformations
>>> that have been applied.
>>
>> In this particular case, the back-mapping problem is pretty minor.
>> IIUC the optimization is that if we have (abusing BASIC notation)
>>
>> 10 GOTO 20
>> 20 GOTO 30
>> 30 ...
>>
>> then in fact the operations at lines 10 and 20 are, from the point of
>> view of the rest of the program, indivisible -- every time you execute
>> 10 you also execute 20, there is no way to tell from outside whether
>> we paused in betwen executing 10 and 20, etc. Effectively we just have
>> a single uber-instruction that does both:
>>
>> (10, 20) GOTO 30
>> 30 ...
>>
>> So from the coverage point of view, just marking line 20 as covered
>> every time line 10 is executed is the Right Thing To Do. From the
>> debugging point of view, a breakpoint set at line 20 should just trip
>> whenever line 10 is executed -- it's not like there's any way to tell
>> whether we're "half way through" the jump sequence or not. It's a
>> pretty solid abstraction.
>
> You've used the word "just" three times, glossing over the fact that we have
> no facility for marking statements as an uber instruction, and you've made
> no proposal for how it might work.

What we have right now is co_lnotab. It encodes a many-to-one mapping
from bytecode locations to line number:

# bytecode offset -> line no
lnotab = {
 0: 10,
 1: 10,
 2: 10,
 3: 11,
 4: 12,
 ...
}

AFAIK, the main operations it supports are (a) given a bytecode
location, return the relevant line (for backtraces etc.), (b) when
executing bytecode, detect transitions from an instruction associated
with one line to an instruction associated with another line (for
sys.settrace, used by coverage and pdb).

def backtrace_lineno(offset):
    return lnotab[offset]

def do_trace(offset1, offset2):
    if lnotab[offset1] != lnotab[offset2]:
        call_trace_fn(lnotab[offset2])

My proposal is to make this a many-to-many mapping:

lnotab = {
  0: {10},
  1: {10},
  2: {10, 11},  # optimized jump
  3: {12},
  ...
}

def backtrace_lineno(offset):
    # if there are multiple linenos, then it's indistinguishable which one the
    # exception occurred on, so just pick one to display
    return min(lnotab[offset])

def do_trace(offset1, offset2):
    for lineno in sorted(lnotab[offset2].difference(lnotab[offset1])):
        call_trace_fn(lineno)

Yes, there is some complexity in practice because currently co_lnotab
is a ridiculously optimized data structure for encoding the
many-to-one mapping, and so some work needs to be done to come up with
a similarly optimized way of encoding a many-to-many mapping. But this
is all fundamentally trivial. "Compactly encoding a dict of sets of
ints" is not the sort of challenge that we should find daunting and
impossible.

> Even if we build (and test!) a way to do
> that, it only covers this particular kind of oddity with optimized code.

Well, this is the only oddity that is causing problems. And future
optimizations might well be covered by my proposed mechanism. Any
optimization that works by taking in a set of line-number-tagged
objects (ast nodes, bytecode instructions, whatever) and spits out a
set of new objects could potentially make use of this -- just set the
lineno annotation on the output objects to be the union of the lineno
annotations on the input objects. Will that actually be enough in
practice? Who knows, we'll have to wait until we get there. Trying to
handle hypothetical future optimizations now is just borrowing
trouble.

And even if we do add a minimal-optimization mode, that shouldn't be
taken as a blank check to stop worrying about the debuggability of the
default-optimization mode, so we'll still need something like this
sooner or later. gdb actually works extremely well on optimized C/C++
code -- sure, sometimes it's a bit confusing and you have to recompile
with -O0 to wrap your head around what's happening, but gdb keeps
working regardless and I almost never bother. And this is because the
C/C++ crowd has spent a lot of time on coming up with solid systems
for describing really really complicated relationships between
compiler output and the original source code -- much worse than the
ones we have to deal with. Just throwing up our hands and giving up
seems like a rather cowardly solution.

-n

-- 
Nathaniel J. Smith
Postdoctoral researcher - Informatics - University of Edinburgh
http://vorpus.org