Opened 9 years ago

Last modified 6 years ago

#6357 enhancement new

LineReceiver uses O(n**2) complexity

Reported by: therve Owned by: therve
Priority: normal Milestone:
Component: core Keywords:
Cc: Hynek Schlawack, zooko@…, Alex Gaynor Branch: linereceiver-complexity-6357
branch-diff, diff-cov, branch-cov, buildbot
Author: therve


LineReceiver holds data received in a string whereas it should use a list. #2611 has a preliminary patch and a benchmark.

Change History (21)

comment:1 Changed 9 years ago by Hynek Schlawack

Cc: Hynek Schlawack added

comment:2 Changed 9 years ago by therve

Owner: set to therve

comment:3 Changed 9 years ago by therve

Author: therve
Branch: branches/linereceiver-complexity-6357

(In [37886]) Branching to 'linereceiver-complexity-6357'

comment:4 Changed 9 years ago by therve

Keywords: review added
Owner: therve deleted

OK, thanks to Ivan's work on #3803, here's a branch which seems to improve things. I've committed a benchmark in lp:twisted-benchmarks, which shows a good improvement. Existing benchmarks like amp and linereceiver are a bit better, and web stays mostly the same.

Build results here:

comment:5 Changed 9 years ago by Jean-Paul Calderone

Owner: set to Jean-Paul Calderone
Status: newassigned

comment:6 Changed 9 years ago by Jean-Paul Calderone

Keywords: review removed
Owner: changed from Jean-Paul Calderone to therve
Status: assignednew
  1. In the news fragment, please say something like "uses quadratic complexity algorithms" or "has quadratic complexity" instead of "uses quadratic complexity".
  2. Can you expand the ivar for _lineBuffer and _buffer? In particular, a few words about what the buffering strategy is would be useful, I think. That is, knowing how the attributes are used and manipulated would be helpful to know in addition to just what their types are.
  3. test_maximumLineLengthRemaining is changed to deliver two bytes more than the maximum length, rather than just one more byte. Did you mean to leave this in? It seems like if it is a necessary change, it reflects a (very slight) breakage of the MAX_LENGTH feature.
  4. The _busyReceiving flag is gone now. I think this means re-entrant behavior is different now. Re-entrant use of LineReceiver is crazy, but and there are no unit tests for what that flag was doing (apparently), but I feel like we shouldn't break this without a very good reason. It probably isn't very hard to re-add? Maybe also with a unit test. :/
  5. Some things that would be nice, but aren't necessary right now:
    1. Could the buffer management operations all be abstracted? eg, in dataReceived, instead of self._buffer.tell(), self._bufferSize() (or even self._bufferObj.size())? Perhaps that would make the dataReceived logic easier to follow, and perhaps even allow dataReceived` to remain unmodified the next time we want to change the buffer implementation.
    2. in _addToBuffer, the 2 passed to the seek call would be better if spelled os.SEEK_END.

Thanks. Please merge after addressing the first 4 points.

comment:7 Changed 9 years ago by therve

Keywords: review added
Owner: therve deleted

I got a bit confused by point 4, so I'm pointing it back for review. Everything handled, otherwise.

Build results here in a bit:

comment:8 Changed 9 years ago by therve

I made some benchmarks with the branch, using the linereceiver and linereceiver_fragmented in lp:twisted-benchmarks. With cpython 2.7, the fragmented case is about 20% faster, but the standard one about 5% slower.

More interestingly, with pypy 2.0b1, both cases are more than 300% slower :/. Considering it was one of the driving factor, I'm not sure what to do.

comment:10 Changed 9 years ago by Glyph

therve, do you know why the standard case is slower? Have you tried running it under a profiler?

I'm wondering if we can get some PyPy people to have a look at this and give us some hints why it degrades performance there.

comment:11 Changed 9 years ago by zooko

Cc: zooko@… added

comment:12 Changed 9 years ago by Alex Gaynor

I'm happy to take a look at it (and in all likelihood, improve PyPy) if someone can link me the actual source of the patch.

comment:13 Changed 9 years ago by Alex Gaynor

Cc: Alex Gaynor added

comment:14 Changed 9 years ago by therve

Alex, the diff is here:

When I talked to fijal, he mentioned that pypy BytesIO was most likely the culprit.

comment:15 Changed 9 years ago by Tom Prince

Keywords: review removed
Owner: set to therve
  1. Looking at the allocations done, without doing any measurements, is see the following: (I'm not sure these want to or need to be fixed)
    1. In _addToBuffer, if the delimiter is entirely in data, then appending data to self._buffer superflous. You could just prepend self._buffer to the first element of splitted.
    2. In constructing the value to pass to lineLengthExceeded, using self.delimiter.join would avoid an extra concatenation.
    3. It looks like you split the data into lines, even when in raw mode. This seems wasteful.
  1. test_longLineWithDelimiter: What are "the right bytes"?
    • Also, is the behavior you are testing the behavior we want to support? In normal usage, it depends on how data is split into packets, which we don't want people depending on.
  2. I'm not entirely sure why _busyReceiving is still needed. I can't see how calling dataReceived rentrantly is a sensible thing to support. In normal usage, it will add some data to a random place further in the stream.
    • I see that exarkun asked for the reentrant behavior. The comments regarding it indicate that this is only significant for returing a value of dataReceived (or really lineReceived, but it also affect raising an exception, or calling setRawMode, or doing anything at all after calling dataReceived.
    • Even if we don't want to break it, perhaps we want to deprecated it?
  3. Have the performance regressions on pypy been addressed? Can you include the results of running the benchmarks before and after here?

Please resubmit for review after addressing at least 2-4.

comment:16 Changed 9 years ago by Tom Prince

#6536 looks like it has a good test that should be included here.

comment:17 Changed 9 years ago by Richard Wall

The doc for _busyReceiving says:

 @ivar _busyReceiving: Flag preventing reentrant calls to dataReceived. It's
only necessary now to support the deprecated behavior of returning a
value in C{dataReceived}

As far as I can see, that behaviour was deprecated over 2 years ago (ticket:2491#comment:43) so perhaps now is the time to remove it.

On the other hand, _busyReceiving seems to have been added in r36239 to address stack errors (#3050). So perhaps that @ivar is incomplete.

Anyway, I started looking at this (and other lineReceiver branches) because I'm interested in changing the way LineReceiver checks self.transport.disconnecting.

It also seems to be involved in the deprecated return value behaviour but also to prevent further calls to protocol.lineReceived when loseConnection has been called.

In ticket:6606#comment:2 exarkun suggested the following change:

getattr(transport, 'disconnecting', False)

Is that something that could be added to this branch?

comment:18 Changed 9 years ago by zooko

Hey folks, I've opened a series of tickets related to this: #6536, #6556, #6557, #6558, #6559.

I generated all of those in the course of writing an alternate patch for this ticket. I would advocate that those tickets (the ones that have patches and unit tests, that is) should be merged to trunk before any patch that attempts to resolve this ticket, and then a patch for this ticket should be rebased to that trunk. This will make the patch that solves this ticket smaller and easier to review, and it will ensure that it doesn't introduce regressions for any of these bugs, since these bugfix patches come with unit tests.

If that's not the way it is going to go, then instead the people responsible for this ticket probably ought to cherry-pick the unit tests out of those tickets.


comment:19 Changed 9 years ago by zooko

For what it is worth, my alternate patch for #6357 is complete, passes all unit tests including all unit tests in those (comment:18) patches, and has undergone extensive profiling, benchmarking, and optimization. One reason that I've stopped work on it is that I started to think the Right Thing To Do is refactor LineReceiver and LineOnlyReceiver to share code instead of having copies or near-copies of code. So, I thought I would wait to see if the bugfix patches (comment:18) get reviewed and merged to trunk, and if so then maybe write a refactoring patch for LineReceiver and LineOnlyReceiver, and then rebase my optimization patch on top of that refactoring, so that it would optimize both of those classes at once.

comment:20 Changed 9 years ago by Jean-Paul Calderone

I just reviewed #6536. Hopefully there will be some more progress on that issue soon. I hope that the result of that work will be that the test suite will be a little more complete and the patch to resolve this ticket can be that much smaller.

comment:21 Changed 6 years ago by Tom Most

Branch: branches/linereceiver-complexity-6357linereceiver-complexity-6357
Note: See TracTickets for help on using tickets.