[issue38891] ShareableList read and write access is O(N), should be O(1)

[Dirk Roorda]

Dirk Roorda  added the comment:

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!

--
nosy: +dirkroorda
Added file: https://bugs.python.org/file49279/report.py

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue38891] ShareableList read and write access is O(N), should be O(1)

[Antoine Pitrou]

Change by Antoine Pitrou :


--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue38891] ShareableList read and write access is O(N), should be O(1)

[Antoine Pitrou]

Antoine Pitrou  added the comment:


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


--
nosy: +pitrou

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue38891] ShareableList read and write access is O(N), should be O(1)

[Antoine Pitrou]

Change by Antoine Pitrou :


--
versions: +Python 3.9 -Python 3.8

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue38891] ShareableList read and write access is O(N), should be O(1)

[Thomas Krennwallner]

Change by Thomas Krennwallner :


--
keywords: +patch
nosy: +tkren
nosy_count: 3.0 -> 4.0
pull_requests: +18343
stage:  -> patch review
pull_request: https://github.com/python/cpython/pull/18996

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue38891] ShareableList read and write access is O(N), should be O(1)

[Dong-hee Na]

Dong-hee Na  added the comment:

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.

--
nosy: +corona10

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue38891] ShareableList read and write access is O(N), should be O(1)

[Jake Northey]

New submission from Jake Northey :

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.

--
components: Library (Lib)
messages: 357239
nosy: Jake Northey, davin
priority: normal
severity: normal
status: open
title: ShareableList read and write access is O(N), should be O(1)
type: performance
versions: Python 3.8

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com