Issue 38891: ShareableList read and write access is O(N), should be O(1)

For an illustration of the performance implications of the __getitem__ and __setitem__ implementation, see the article below.
https://medium.com/@rvprasad/performance-of-system-v-style-shared-memory-support-in-python-3-8-d7a7d1b1fb96

The issue appears to be due to the summing of ShareableList item sizes to generate an offset for the requested item.  Perhaps an offset-based index could be created in which the allocation sizes could be constructed by comparing two offets.

IMHO,

1. replace self._allocated_bytes to self._sum_allocated_bytes
2. initialize self._sum_allocated_bytes at the __init__ time.
2. if self._allocated_bytes is needed, calculate from _sum_allocated_bytes it will take O(1)

If the suggestion is accepted, I'd like to work on this issue.

New changeset c8f1715283ec51822fb37a702bf253cbac1af276 by Thomas Krennwallner in branch 'master':
bpo-38891: avoid quadratic item access performance of ShareableList (GH-18996)
https://github.com/python/cpython/commit/c8f1715283ec51822fb37a702bf253cbac1af276

I can see that the performance of ShareableList is much better now.
Still the performance of list operations on a ShareableList may be degraded by a factor 200-300 with respect to a normal list.

If this is unavoidable then the docs should clearly mention this degradation, because this will, in many use cases, cancel the performance gain that shared memory offers!

pull_requests: + pull_request18343
stage: patch review