Making CallStack immutable, so it can be hashable

Making CallStack immutable, so it can be hashable

To use loglinear models for classifying CLs, we need CallStack and Stacktrace to be valid argument types for MemoizedFunction, which means they must be hashable, which means they must be immutable. This CL makes CallStack immutable (a separate CL will handle Stacktrace).

BUG=
TBR=stgao@chromium.org

Review-Url: https://codereview.chromium.org/2562623004
Committed: https://chromium.googlesource.com/infra/infra/+/cdf1d3bfc59fd7d31bd4cdee58a9055c09954562

[wrengr, 2016-12-08 19:25:03]

Description was changed from

==========
[WIP] Making CallStack and Stacktrace immutable, so they can be hashable

This CL is currewntly in progress, so not ready for review.

BUG=
==========

to

==========
Making CallStack immutable, so it can be hashable

When using loglinear models in practice we need CallStack and Stacktrace to be
hashable, so they can be arguments to MemoizedFunctions. In order to be
hashable, they must be immutable. This CL makes CallStack immutable (a separate
CL will handle Stacktrace).

BUG=
TBR=stgao@chromium.org
==========

[wrengr, 2016-12-08 19:25:03]

wrengr@chromium.org changed reviewers:
+ inferno@chromium.org, katesonia@chromium.org, mbarbella@chromium.org

[wrengr, 2016-12-08 19:25:30]

Description was changed from

==========
Making CallStack immutable, so it can be hashable

When using loglinear models in practice we need CallStack and Stacktrace to be
hashable, so they can be arguments to MemoizedFunctions. In order to be
hashable, they must be immutable. This CL makes CallStack immutable (a separate
CL will handle Stacktrace).

BUG=
TBR=stgao@chromium.org
==========

to

==========
Making CallStack immutable, so it can be hashable

To use loglinear models for classifying CLs, we need CallStack and Stacktrace to
be hashable, so they can be arguments to MemoizedFunctions. In order to be
hashable, they must be immutable. This CL makes CallStack immutable (a separate
CL will handle Stacktrace).

BUG=
TBR=stgao@chromium.org
==========

[wrengr, 2016-12-08 19:26:19]

Description was changed from

==========
Making CallStack immutable, so it can be hashable

To use loglinear models for classifying CLs, we need CallStack and Stacktrace to
be hashable, so they can be arguments to MemoizedFunctions. In order to be
hashable, they must be immutable. This CL makes CallStack immutable (a separate
CL will handle Stacktrace).

BUG=
TBR=stgao@chromium.org
==========

to

==========
Making CallStack immutable, so it can be hashable

To use loglinear models for classifying CLs, we need CallStack and Stacktrace to
be valid arguments to MemoizedFunctions, which means they must be hashable,
which means they must be immutable. This CL makes CallStack immutable (a
separate CL will handle Stacktrace).

BUG=
TBR=stgao@chromium.org
==========

[wrengr, 2016-12-08 19:26:37]

Description was changed from

==========
Making CallStack immutable, so it can be hashable

To use loglinear models for classifying CLs, we need CallStack and Stacktrace to
be valid arguments to MemoizedFunctions, which means they must be hashable,
which means they must be immutable. This CL makes CallStack immutable (a
separate CL will handle Stacktrace).

BUG=
TBR=stgao@chromium.org
==========

to

==========
Making CallStack immutable, so it can be hashable

To use loglinear models for classifying CLs, we need CallStack and Stacktrace to
be valid argument types for MemoizedFunction, which means they must be hashable,
which means they must be immutable. This CL makes CallStack immutable (a
separate CL will handle Stacktrace).

BUG=
TBR=stgao@chromium.org
==========

[wrengr, 2016-12-08 19:27:02]

Patchset #1 (id:1) has been deleted

[wrengr, 2016-12-08 19:27:28]

PTAL

[Sharu Jiang, 2016-12-08 22:23:44]

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
File appengine/findit/crash/stacktrace.py (right):

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:85: # method on ``StackFrame``.
I think in ``StackFrame`` and change the name to Parse should be the way to go.

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:166: # memoization) we has-a tuple rather
than is-a list.
I think it's not necessary to make every parameter to memorized function
immutable. If you use the cache decorator in
https://cs.chromium.org/chromium/infra/appengine/findit/libs/cache_decorator.py,
we have something like _DefaultKeyGenerator(You can define yours to serve your
purpose) to generate key.
 
Another concern is that we do a lot manipulation to CallStack and StackTrace,
e.g. a lot filtering. Making it immutable will slow down the efficiency.

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:253: # TODO(wrengr): can we use
``_replace`` without running into TypeErrors?
what TypeErrors you encountered?

[Martin Barbella, 2016-12-08 22:30:55]

Mostly nits. LGTM overall.

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
File appengine/findit/crash/changelist_classifier.py (right):

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/changelist_classifier.py:61: # TODO(wrengr): use
CallStack.SliceFrames
Nit: end with period. Also, is there a reason not to do this in this CL? Are
there any other complications related to it?

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
File appengine/findit/crash/stacktrace.py (right):

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:53: assert index is not None,
TypeError("The index must be an int")
Nit: single quotes for consistency with other strings.

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:85: # method on ``StackFrame``.
On 2016/12/08 22:23:44, Sharu Jiang wrote:
> I think in ``StackFrame`` and change the name to Parse should be the way to
go.

Is there any reason not to just do this (my usual comment for new TODOs)?

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:213: if format_type ==
CallStackFormatType.JAVA: # pragma: no cover
Not too important, but do we really need no cover here? Seems like an easy
enough case to hit, but there might not be much value in it.

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:226: # TODO: we do actually have unittests
for this, but for some reason
Strange. Is there a bug opened for this? might be nice to be able to point folks
more familiar with how we gather the coverage information at this.

Also, could you reference the bug or yourself in the TODO?

[stgao, 2016-12-08 23:42:17]

stgao@chromium.org changed reviewers:
+ stgao@chromium.org

[stgao, 2016-12-08 23:42:17]

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
File appengine/findit/crash/stacktrace.py (right):

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:85: # method on ``StackFrame``.
On 2016/12/08 22:30:55, Martin Barbella wrote:
> On 2016/12/08 22:23:44, Sharu Jiang wrote:
> > I think in ``StackFrame`` and change the name to Parse should be the way to
> go.
> 
> Is there any reason not to just do this (my usual comment for new TODOs)?

Let's make this a method into the class in this CL instead of a TODO.
If it is a question to discuss during code-review, it is better to add as a
comment before publishing the CL.

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:166: # memoization) we has-a tuple rather
than is-a list.
On 2016/12/08 22:23:44, Sharu Jiang wrote:
> I think it's not necessary to make every parameter to memorized function
> immutable. If you use the cache decorator in
>
https://cs.chromium.org/chromium/infra/appengine/findit/libs/cache_decorator.py,
> we have something like _DefaultKeyGenerator(You can define yours to serve your
> purpose) to generate key.

With the current implementation of MemoizedFunction, I agree that an in-memory
cache + a customized key generator (the default one might work as well) could do
the same, as I commented in the CL which added MemoizedFunction. We could add a
new API to clear the cache.

But I'd like to see the usage of MemoizedFunction to understand better.
wrengr@, do you have some code snippet on where and how MemoizedFunction will be
used?

>  
> Another concern is that we do a lot manipulation to CallStack and StackTrace,
> e.g. a lot filtering. Making it immutable will slow down the efficiency.

This is a problem we need to discuss as it is impacted by this CL. This might
cause test breakage as is?

Overall, read-only namedtuple could help avoid the surprise of unexpected
modification.
But as we currently modify the stack trace in-place when we filter out some
frames, we need to think on the overhead of deepcopy for modification.

wrengr@, what do you think of such overhead?

katesonia@, is it doable to do filtering before creating CallStack instance?

[wrengr, 2016-12-08 23:42:36]

wrengr@chromium.org changed reviewers:
- stgao@chromium.org

[wrengr, 2016-12-08 23:42:37]

Addressed nits

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
File appengine/findit/crash/changelist_classifier.py (right):

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/changelist_classifier.py:61: # TODO(wrengr): use
CallStack.SliceFrames
On 2016/12/08 22:30:55, Martin Barbella wrote:
> Nit: end with period. Also, is there a reason not to do this in this CL? Are
> there any other complications related to it?

Done.

FWIW, most of the time when I'm making todo notes they are things I intend to
put in the current CL; it's just a note to myself so I don't forget to do it.
E.g., this one was made before I'd actually written SliceFrames :)

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
File appengine/findit/crash/stacktrace.py (right):

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:53: assert index is not None,
TypeError("The index must be an int")
On 2016/12/08 22:30:55, Martin Barbella wrote:
> Nit: single quotes for consistency with other strings.

Done.

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:85: # method on ``StackFrame``.
On 2016/12/08 22:30:55, Martin Barbella wrote:
> On 2016/12/08 22:23:44, Sharu Jiang wrote:
> > I think in ``StackFrame`` and change the name to Parse should be the way to
> go.
> 
> Is there any reason not to just do this (my usual comment for new TODOs)?

Mainly just that I ran into issues getting it to work when I first tried it.
(Also not sure if people had preferences on where to put it.) Done now.

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:166: # memoization) we has-a tuple rather
than is-a list.
On 2016/12/08 22:23:44, Sharu Jiang wrote:
> I think it's not necessary to make every parameter to memorized function
> immutable. If you use the cache decorator in
>
https://cs.chromium.org/chromium/infra/appengine/findit/libs/cache_decorator.py,
> we have something like _DefaultKeyGenerator(You can define yours to serve your
> purpose) to generate key.
>  
> Another concern is that we do a lot manipulation to CallStack and StackTrace,
> e.g. a lot filtering. Making it immutable will slow down the efficiency.

Even though the old code did do a lot of mutation, it actually doesn't need to.
There are two places where we call SliceFrames: (1) when computing the
crash_stack for a Stacktrace, which is done only once per construction of a
StackTrace, (2) in the CL classifier for limiting what all the scorers/features
look at, which isn't really necessary since the scorers/features can be
redesigned to only look at the top few frames.

If we actually do run into performance issues then we can optimize the
SliceFrames method. Since things are mutable all the way down, we shouldn't
actually have to allocate a new tuple and copy the pointers to StackFrames over.
We can do a lightweight slicing by just storing a pointer to the original tuple
plus information about the starting and stopping indices. It's trivial enough to
do; but I'd wait to see if we actually have performance issues before bothering.

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:213: if format_type ==
CallStackFormatType.JAVA: # pragma: no cover
On 2016/12/08 22:30:55, Martin Barbella wrote:
> Not too important, but do we really need no cover here? Seems like an easy
> enough case to hit, but there might not be much value in it.

We don't *need* the pragma; rather, the old version of the code wasn't actually
covering this case, but that was hidden from the code coverage checker.

Added a new test.

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:226: # TODO: we do actually have unittests
for this, but for some reason
On 2016/12/08 22:30:55, Martin Barbella wrote:
> Strange. Is there a bug opened for this? might be nice to be able to point
folks
> more familiar with how we gather the coverage information at this.
> 
> Also, could you reference the bug or yourself in the TODO?

Done. crbug.com/672641

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:253: # TODO(wrengr): can we use
``_replace`` without running into TypeErrors?
On 2016/12/08 22:23:44, Sharu Jiang wrote:
> what TypeErrors you encountered?

The TypeError complains about _make not being called with the right number of
arguments (_make is called by _replace). It's something really weird about the
guts of namedtuples and not easily googleable. I'm guessing it has something to
do with the fact that the frames attribute is a tuple rather than a simple
scalar, and that we're changing its length. If I can trigger it again I'll file
a bug with the stack trace.

Copying all the other attributes over one by one works well enough; it just
introduces maintenance costs should we ever change the arguments to the
constructor

[Sharu Jiang, 2016-12-09 00:13:58]

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
File appengine/findit/crash/stacktrace.py (right):

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:166: # memoization) we has-a tuple rather
than is-a list.
On 2016/12/08 23:42:17, stgao (slow on Monday) wrote:
> On 2016/12/08 22:23:44, Sharu Jiang wrote:
> > I think it's not necessary to make every parameter to memorized function
> > immutable. If you use the cache decorator in
> >
>
https://cs.chromium.org/chromium/infra/appengine/findit/libs/cache_decorator.py,
> > we have something like _DefaultKeyGenerator(You can define yours to serve
your
> > purpose) to generate key.
> 
> With the current implementation of MemoizedFunction, I agree that an in-memory
> cache + a customized key generator (the default one might work as well) could
do
> the same, as I commented in the CL which added MemoizedFunction. We could add
a
> new API to clear the cache.
> 
> But I'd like to see the usage of MemoizedFunction to understand better.
> wrengr@, do you have some code snippet on where and how MemoizedFunction will
be
> used?
> 
> >  
> > Another concern is that we do a lot manipulation to CallStack and
StackTrace,
> > e.g. a lot filtering. Making it immutable will slow down the efficiency.
> 
> This is a problem we need to discuss as it is impacted by this CL. This might
> cause test breakage as is?
> 
> Overall, read-only namedtuple could help avoid the surprise of unexpected
> modification.
> But as we currently modify the stack trace in-place when we filter out some
> frames, we need to think on the overhead of deepcopy for modification.
> 
> wrengr@, what do you think of such overhead?
> 
> katesonia@, is it doable to do filtering before creating CallStack instance?

We can do, that's one alternative, but this will need some redesign on the
stacktrace Parser.

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:166: # memoization) we has-a tuple rather
than is-a list.
On 2016/12/08 23:42:37, wrengr wrote:
> On 2016/12/08 22:23:44, Sharu Jiang wrote:
> > I think it's not necessary to make every parameter to memorized function
> > immutable. If you use the cache decorator in
> >
>
https://cs.chromium.org/chromium/infra/appengine/findit/libs/cache_decorator.py,
> > we have something like _DefaultKeyGenerator(You can define yours to serve
your
> > purpose) to generate key.
> >  
> > Another concern is that we do a lot manipulation to CallStack and
StackTrace,
> > e.g. a lot filtering. Making it immutable will slow down the efficiency.
> 
> Even though the old code did do a lot of mutation, it actually doesn't need
to.
> There are two places where we call SliceFrames: (1) when computing the
> crash_stack for a Stacktrace, which is done only once per construction of a
> StackTrace, (2) in the CL classifier for limiting what all the
scorers/features
> look at, which isn't really necessary since the scorers/features can be
> redesigned to only look at the top few frames.

For those frames we don't even look into, we shouldn't waste memory to keep
them. Or an alternative should be to redesign the stacktrace to only parse
frames after the signature frame. 


> If we actually do run into performance issues then we can optimize the
> SliceFrames method. Since things are mutable all the way down, we shouldn't
> actually have to allocate a new tuple and copy the pointers to StackFrames
over.
> We can do a lightweight slicing by just storing a pointer to the original
tuple
> plus information about the starting and stopping indices. It's trivial enough
to
> do; but I'd wait to see if we actually have performance issues before
bothering.

One thing is, do you really want to force every parameter of MemerizedFunction
to be immutable? Especially the ``Callstack`` and ``Stacktrace`` are not small,
using them as key may not be very efficient. IMHO, it'd be better to reuse the
cache_decorator and cache, or you can add key generator to MemorizedFunctions.

[Sharu Jiang, 2016-12-09 00:29:21]

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
File appengine/findit/crash/stacktrace.py (right):

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:166: # memoization) we has-a tuple rather
than is-a list.
On 2016/12/09 00:13:58, Sharu Jiang wrote:
> On 2016/12/08 23:42:37, wrengr wrote:
> > On 2016/12/08 22:23:44, Sharu Jiang wrote:
> > > I think it's not necessary to make every parameter to memorized function
> > > immutable. If you use the cache decorator in
> > >
> >
>
https://cs.chromium.org/chromium/infra/appengine/findit/libs/cache_decorator.py,
> > > we have something like _DefaultKeyGenerator(You can define yours to serve
> your
> > > purpose) to generate key.
> > >  
> > > Another concern is that we do a lot manipulation to CallStack and
> StackTrace,
> > > e.g. a lot filtering. Making it immutable will slow down the efficiency.
> > 
> > Even though the old code did do a lot of mutation, it actually doesn't need
> to.
> > There are two places where we call SliceFrames: (1) when computing the
> > crash_stack for a Stacktrace, which is done only once per construction of a
> > StackTrace, (2) in the CL classifier for limiting what all the
> scorers/features
> > look at, which isn't really necessary since the scorers/features can be
> > redesigned to only look at the top few frames.
> 
> For those frames we don't even look into, we shouldn't waste memory to keep
> them. Or an alternative should be to redesign the stacktrace to only parse
> frames after the signature frame. 

*Only parse top_n frames after the signature frame.

> 
> 
> > If we actually do run into performance issues then we can optimize the
> > SliceFrames method. Since things are mutable all the way down, we shouldn't
> > actually have to allocate a new tuple and copy the pointers to StackFrames
> over.
> > We can do a lightweight slicing by just storing a pointer to the original
> tuple
> > plus information about the starting and stopping indices. It's trivial
enough
> to
> > do; but I'd wait to see if we actually have performance issues before
> bothering.
> 
> One thing is, do you really want to force every parameter of MemerizedFunction
> to be immutable? Especially the ``Callstack`` and ``Stacktrace`` are not
small,
> using them as key may not be very efficient. IMHO, it'd be better to reuse the

Ignore "using them as key may not be very efficient" comment, the namedtuple
hash should have solved this... 

> cache_decorator and cache, or you can add key generator to MemorizedFunctions.

I saw your comments in https://codereview.chromium.org/2557423003/, if
optimization can solve the performance issue, but a question, for general
purpose, is forcing the parameter x of MemorizedFunction immutable good?

[Sharu Jiang, 2016-12-09 00:57:15]

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
File appengine/findit/crash/stacktrace.py (right):

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:166: # memoization) we has-a tuple rather
than is-a list.
On 2016/12/09 00:29:20, Sharu Jiang wrote:
> On 2016/12/09 00:13:58, Sharu Jiang wrote:
> > On 2016/12/08 23:42:37, wrengr wrote:
> > > On 2016/12/08 22:23:44, Sharu Jiang wrote:
> > > > I think it's not necessary to make every parameter to memorized function
> > > > immutable. If you use the cache decorator in
> > > >
> > >
> >
>
https://cs.chromium.org/chromium/infra/appengine/findit/libs/cache_decorator.py,
> > > > we have something like _DefaultKeyGenerator(You can define yours to
serve
> > your
> > > > purpose) to generate key.
> > > >  
> > > > Another concern is that we do a lot manipulation to CallStack and
> > StackTrace,
> > > > e.g. a lot filtering. Making it immutable will slow down the efficiency.
> > > 
> > > Even though the old code did do a lot of mutation, it actually doesn't
need
> > to.
> > > There are two places where we call SliceFrames: (1) when computing the
> > > crash_stack for a Stacktrace, which is done only once per construction of
a
> > > StackTrace, (2) in the CL classifier for limiting what all the
> > scorers/features
> > > look at, which isn't really necessary since the scorers/features can be
> > > redesigned to only look at the top few frames.
> > 
> > For those frames we don't even look into, we shouldn't waste memory to keep
> > them. Or an alternative should be to redesign the stacktrace to only parse
> > frames after the signature frame. 
> 
> *Only parse top_n frames after the signature frame.
> 
> > 
> > 
> > > If we actually do run into performance issues then we can optimize the
> > > SliceFrames method. Since things are mutable all the way down, we
shouldn't
> > > actually have to allocate a new tuple and copy the pointers to StackFrames
> > over.
> > > We can do a lightweight slicing by just storing a pointer to the original
> > tuple
> > > plus information about the starting and stopping indices. It's trivial
> enough
> > to
> > > do; but I'd wait to see if we actually have performance issues before
> > bothering.
> > 
> > One thing is, do you really want to force every parameter of
MemerizedFunction
> > to be immutable? Especially the ``Callstack`` and ``Stacktrace`` are not
> small,
> > using them as key may not be very efficient. IMHO, it'd be better to reuse
the
> 
> Ignore "using them as key may not be very efficient" comment, the namedtuple
> hash should have solved this... 
> 
> > cache_decorator and cache, or you can add key generator to
MemorizedFunctions.
> 
> I saw your comments in https://codereview.chromium.org/2557423003/, if
> optimization can solve the performance issue, but a question, for general
> purpose, is forcing the parameter x of MemorizedFunction immutable good?
> 
> 

Follow up on "redesign the stacktrace to only parse
top_n frames after the signature frame.", this would make parsing stacktrace
depend on ``top_n`` in config, this may mess our core_algorithm/gae stuff
seperation...

[wrengr, 2016-12-09 18:58:05]

On 2016/12/09 00:13:58, Sharu Jiang wrote:
> One thing is, do you really want to force every parameter of MemerizedFunction
> to be immutable?

Yes. The idea behind MemoizedFunction (and Function) is that they are
mathematical functions, that is they always take the same input to the same
output. Mutating the inputs means we're passing different inputs, therefore the
output may also need to be mutated; and that way lies madness. For the intended
purpose of MemoizedFunction, requiring hashable inputs isn't a limitation.


> Especially the ``Callstack`` and ``Stacktrace`` are not small,
> using them as key may not be very efficient.

Python's dict is a hash table, therefore all the keys are actually stored/looked
up by their hash. The actual size of the keys is only relevant if we encounter a
whole bunch of hash collisions. All this focusing on the precise performance
details of memoization is premature. The current implementation is the simplest
thing that works, and therefore from a maintenance and technical debt
perspective it's to be preferred. I've spent all my time so far paying down
technical debt, so I don't want to add any more. We have no evidence that the
current implementation is in fact (a) inefficient, nor (b) the actual bottleneck
for whole-program performance. If in the future we determine that the current
implementation of memoization really is the bottleneck, we can change the
implementation at that point.


> [...] MemerizedFunction [...] MemorizedFunctions [...]

That's "memo-ized", like we're keeping memos around.

[wrengr, 2016-12-09 18:58:38]

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
File appengine/findit/crash/stacktrace.py (right):

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:166: # memoization) we has-a tuple rather
than is-a list.
On 2016/12/08 23:42:17, stgao (slow on Monday) wrote:
> This is a problem we need to discuss as it is impacted by this CL. This might
> cause test breakage as is?

All tests pass with 100% coverage. The only modifications were to remove the
unnecessary mutation. (A lot of tests would allocate an empty stack and then
push a whole bunch of frames onto it; now they allocate the complete stack in
one go, which they should've done in the first place.)


> Overall, read-only namedtuple could help avoid the surprise of unexpected
> modification.

Yes, I agree. Semantically callstacks/stacktraces aren't things that change;
they're just information given to us to look at.


> But as we currently modify the stack trace in-place when we filter out some
> frames, we need to think on the overhead of deepcopy for modification.

Because things are immutable all the way down, there's no need for deep copy.
The only thing SliceFrames needs to do is (1) allocate the new namedtuple, (2)
allocate a tuple for the frames we want to keep, (3) copy pointers. The first
and third are unavoidable; but as I mentioned elsewhere, the second is an
avoidable artifact of the current implementation.

That is, rather than allocating a new tuple for the frames and copying over all
the pointers to those frames, we can instead have a namedtuple which does a
"soft copy". That is, the soft copy stores three things: a pointer to the
original tuple, start index, stop index; and provides the same API as if we did
the hard copy. This reduces the cost of slicing down to be constant time. This
is a standard trick used extensively in other languages (and maybe that's what
Python's "slice objects" do?). But since it adds complexity, I'd rather wait and
see whether we actually need to bother doing it (given as we only call
SliceFrames in two places, so it's not like we're doing this all that often).

https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
appengine/findit/crash/stacktrace.py:166: # memoization) we has-a tuple rather
than is-a list.
On 2016/12/08 23:42:17, stgao (slow on Monday) wrote:
> With the current implementation of MemoizedFunction, I agree that an in-memory
> cache + a customized key generator (the default one might work as well) could
do
> the same, as I commented in the CL which added MemoizedFunction. We could add
a
> new API to clear the cache.
> 
> But I'd like to see the usage of MemoizedFunction to understand better.
> wrengr@, do you have some code snippet on where and how MemoizedFunction will
be
> used?

The code using MemoizedFunction is:

https://codereview.chromium.org/2517383005/
https://codereview.chromium.org/2544493004/

The code necessitating this CL is:

https://codereview.chromium.org/2560723005/

[Sharu Jiang, 2016-12-09 19:47:19]

On 2016/12/09 18:58:38, wrengr wrote:
>
https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
> File appengine/findit/crash/stacktrace.py (right):
> 
>
https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
> appengine/findit/crash/stacktrace.py:166: # memoization) we has-a tuple rather
> than is-a list.
> On 2016/12/08 23:42:17, stgao (slow on Monday) wrote:
> > This is a problem we need to discuss as it is impacted by this CL. This
might
> > cause test breakage as is?
> 
> All tests pass with 100% coverage. The only modifications were to remove the
> unnecessary mutation. (A lot of tests would allocate an empty stack and then
> push a whole bunch of frames onto it; now they allocate the complete stack in
> one go, which they should've done in the first place.)
> 
> 
> > Overall, read-only namedtuple could help avoid the surprise of unexpected
> > modification.
> 
> Yes, I agree. Semantically callstacks/stacktraces aren't things that change;
> they're just information given to us to look at.
> 
> 
> > But as we currently modify the stack trace in-place when we filter out some
> > frames, we need to think on the overhead of deepcopy for modification.
> 
> Because things are immutable all the way down, there's no need for deep copy.
> The only thing SliceFrames needs to do is (1) allocate the new namedtuple, (2)
> allocate a tuple for the frames we want to keep, (3) copy pointers. The first
> and third are unavoidable; but as I mentioned elsewhere, the second is an
> avoidable artifact of the current implementation.
> 
> That is, rather than allocating a new tuple for the frames and copying over
all
> the pointers to those frames, we can instead have a namedtuple which does a
> "soft copy". That is, the soft copy stores three things: a pointer to the
> original tuple, start index, stop index; and provides the same API as if we
did
> the hard copy. This reduces the cost of slicing down to be constant time. This
> is a standard trick used extensively in other languages (and maybe that's what
> Python's "slice objects" do?). But since it adds complexity, I'd rather wait
and

Just searched, x[i:j] takes time and space proportional to j-i; a new and
independent object is created.

> see whether we actually need to bother doing it (given as we only call
> SliceFrames in two places, so it's not like we're doing this all that often).
> 
>
https://codereview.chromium.org/2562623004/diff/20001/appengine/findit/crash/...
> appengine/findit/crash/stacktrace.py:166: # memoization) we has-a tuple rather
> than is-a list.
> On 2016/12/08 23:42:17, stgao (slow on Monday) wrote:
> > With the current implementation of MemoizedFunction, I agree that an
in-memory
> > cache + a customized key generator (the default one might work as well)
could
> do
> > the same, as I commented in the CL which added MemoizedFunction. We could
add
> a
> > new API to clear the cache.
> > 
> > But I'd like to see the usage of MemoizedFunction to understand better.
> > wrengr@, do you have some code snippet on where and how MemoizedFunction
will
> be
> > used?
> 
> The code using MemoizedFunction is:
> 
> https://codereview.chromium.org/2517383005/
> https://codereview.chromium.org/2544493004/
> 
> The code necessitating this CL is:
> 
> https://codereview.chromium.org/2560723005/

[Sharu Jiang, 2016-12-09 20:43:28]

lgtm 

About the filtering on immutable callstack, I don't think this will be a bottom
neck of performance but it's something we can observe and potentially optimize
:)

[wrengr, 2016-12-12 17:54:54]

The CQ bit was checked by wrengr@chromium.org

[wrengr, 2016-12-12 17:54:55]

The patchset sent to the CQ was uploaded after l-g-t-m from
mbarbella@chromium.org
Link to the patchset: https://codereview.chromium.org/2562623004/#ps60001
(title: "Addressing nits")

[commit-bot: I haz the power, 2016-12-12 17:55:04]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-12-12 18:11:22]

CQ is committing da patch.

Bot data: {"patchset_id": 60001, "attempt_start_ts": 1481565294599200,
"parent_rev": "decae1da1d563e156417de15cbee336f37e09cb3", "commit_rev":
"cdf1d3bfc59fd7d31bd4cdee58a9055c09954562"}

[commit-bot: I haz the power, 2016-12-12 18:11:25]

Description was changed from

==========
Making CallStack immutable, so it can be hashable

To use loglinear models for classifying CLs, we need CallStack and Stacktrace to
be valid argument types for MemoizedFunction, which means they must be hashable,
which means they must be immutable. This CL makes CallStack immutable (a
separate CL will handle Stacktrace).

BUG=
TBR=stgao@chromium.org
==========

to

==========
Making CallStack immutable, so it can be hashable

To use loglinear models for classifying CLs, we need CallStack and Stacktrace to
be valid argument types for MemoizedFunction, which means they must be hashable,
which means they must be immutable. This CL makes CallStack immutable (a
separate CL will handle Stacktrace).

BUG=
TBR=stgao@chromium.org

Review-Url: https://codereview.chromium.org/2562623004
Committed:
https://chromium.googlesource.com/infra/infra/+/cdf1d3bfc59fd7d31bd4cdee58a90...
==========

[commit-bot: I haz the power, 2016-12-12 18:11:26]

Committed patchset #3 (id:60001) as
https://chromium.googlesource.com/infra/infra/+/cdf1d3bfc59fd7d31bd4cdee58a90...