classification
Title: ShareableList read and write access is O(N), should be O(1)
Type: performance Stage: resolved
Components: Library (Lib) Versions: Python 3.9
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Jake Northey, corona10, davin, dirkroorda, pitrou, tkren
Priority: normal Keywords: patch

Created on 2019-11-22 02:31 by Jake Northey, last changed 2020-06-30 08:43 by dirkroorda. This issue is now closed.

Files
File name Uploaded Description Edit
report.py dirkroorda, 2020-06-30 08:43 Test of computing max of a shareable list of several sizes, timings for python 3.8.3 and 3.9.0b3
Pull Requests
URL Status Linked Edit
PR 18996 merged tkren, 2020-03-14 14:57
Messages (4)
msg357239 - (view) Author: Jake Northey (Jake Northey) Date: 2019-11-22 02:31
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.
msg357262 - (view) Author: Dong-hee Na (corona10) * (Python committer) Date: 2019-11-22 09:45
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.
msg366784 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2020-04-19 15:19
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
msg372665 - (view) Author: Dirk Roorda (dirkroorda) * Date: 2020-06-30 08:43
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!
History
Date User Action Args
2020-06-30 08:43:24dirkroordasetfiles: + report.py
nosy: + dirkroorda
messages: + msg372665

2020-04-19 15:19:42pitrousetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2020-04-19 15:19:28pitrousetnosy: + pitrou
messages: + msg366784
2020-04-18 18:39:27pitrousetversions: + Python 3.9, - Python 3.8
2020-03-14 14:57:40tkrensetkeywords: + patch
nosy: + tkren

pull_requests: + pull_request18343
stage: patch review
2019-11-22 09:45:31corona10setnosy: + corona10
messages: + msg357262
2019-11-22 02:31:14Jake Northeycreate