Issue1949
Created on 2012-07-23.22:10:02 by duffy151, last changed 2014-06-23.17:52:08 by zyasoft.
File name |
Uploaded |
Description |
Edit |
Remove |
issue1949.patch
|
santa4nt,
2014-06-08.16:35:07
|
Add 'maxlen' attribute as an upper bound to a deque's size. |
|
|
issue1949.patch
|
santa4nt,
2014-06-08.18:24:04
|
Refreshing patch. Implement some more missing methods from Python 2.7 version of deque. |
|
|
issue1949.patch
|
santa4nt,
2014-06-08.21:08:33
|
Patch refresh. |
|
|
issue1949.patch
|
santa4nt,
2014-06-09.19:12:28
|
Patch refresh. All missing methods implemented. All unit tests passed. |
|
|
issue1949.patch
|
santa4nt,
2014-06-09.23:22:32
|
Patch refresh. Adding test_deque_jy for thread safety tests. |
|
|
msg7334 (view) |
Author: Kevin Duffy (duffy151) |
Date: 2012-07-23.22:10:02 |
|
Referring to http://docs.python.org/library/collections.html#collections.deque , deque() should take a maxlen keyword arg to enable a ringbuffer / bounded length deque.
Jython:
Jython 2.7a2 (default:9c148a201233, May 24 2012, 15:49:00)
[Java HotSpot(TM) 64-Bit Server VM (Apple Inc.)] on java1.6.0_33
Type "help", "copyright", "credits" or "license" for more information.
>>> from collections import deque
>>> deque(maxlen=10)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: deque() does not take keyword arguments
>>>
CPython:
Python 2.7.3 (default, Jul 9 2012, 10:36:52)
[GCC 4.2.1 Compatible Apple Clang 4.0 (tags/Apple/clang-418.0.60)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from collections import deque
>>> deque(maxlen=10)
deque([], maxlen=10)
>>>
|
msg7538 (view) |
Author: Irmen de Jong (irmen) |
Date: 2012-11-27.22:39:11 |
|
I'm encountering this problem as well.
|
msg8510 (view) |
Author: Jim Baker (zyasoft) |
Date: 2014-05-21.23:57:18 |
|
Target beta 4
|
msg8602 (view) |
Author: Santoso Wijaya (santa4nt) |
Date: 2014-06-08.01:15:00 |
|
Lib/test/test_deque.py and lib-python/2.7/test/test_deque.py have diverged significantly. Running the latter produces 3 failures and 9 errors with the current Jython 2.7.x snapshot.
|
msg8603 (view) |
Author: Santoso Wijaya (santa4nt) |
Date: 2014-06-08.16:35:07 |
|
Attaching a patch to add the missing 'maxlen' attribute.
This brings down test_deque from lib-python/2.7/... to 3 failures and 7 errors. There are still a couple more missing methods/attributes and other behavioral issues.
|
msg8604 (view) |
Author: Jim Baker (zyasoft) |
Date: 2014-06-08.17:04:42 |
|
We need to revisit the implementation of deque. Per https://docs.python.org/2/library/collections.html#collections.deque, operations are threadsafe. We do not currently implement this threadsafety requirement in Jython's implementation.
For the unbounded case, we should use http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentLinkedDeque.html, which is new with Java 7. This seems to be a more or less exact match.
For the bounded case (with maxlen), the discard semantics are interesting and certainly not those of a synchronized ArrayDeque. We probably want to use an array of PyObject of size maxlen; then implement synchronized methods.
Exposing both approaches with the same API will require a modest amount of cleverness.
|
msg8605 (view) |
Author: Santoso Wijaya (santa4nt) |
Date: 2014-06-08.18:24:04 |
|
Refreshing patch. Implement some more missing methods from Python 2.7 version of deque.
This brings test result from lib-python/2.7/test/test_deque.py to only 4 failures and no error.
|
msg8606 (view) |
Author: Santoso Wijaya (santa4nt) |
Date: 2014-06-08.18:26:13 |
|
@zyasoft. Why not keep the current doubly-linked nodes implementation and simply synchronize the methods we expose?
|
msg8607 (view) |
Author: Santoso Wijaya (santa4nt) |
Date: 2014-06-08.18:38:00 |
|
@zyasoft, that is, the `header` object in our current implementation is already ever-present and acts as a sentinel for the deque's linked-nodes structure.
I think we can use that as a synchronizing lock for our methods.
|
msg8608 (view) |
Author: Santoso Wijaya (santa4nt) |
Date: 2014-06-08.19:22:17 |
|
Additionally, the "thread safety" of collections.deque in CPython is so only because it is implemented in C, so the GIL takes care that only one thread can call a method on a deque object at a given time, thereby ensuring that states are updated atomically within a single C function. Looking at CPython's implementation of deque, there is no additional concurrency constructs other than relying on the GIL.
|
msg8609 (view) |
Author: Santoso Wijaya (santa4nt) |
Date: 2014-06-08.21:08:33 |
|
Another patch refresh. Passes all but 1 test in lib/2.7/test/test_deque.py (due to an unimplemented deque.reverse() method).
|
msg8610 (view) |
Author: Jim Baker (zyasoft) |
Date: 2014-06-09.04:17:36 |
|
Santoso, fair enough re synchronizing the current implementation. In general we have chosen java.util.concurrent where it can support core structures like dict, but deque is used comparatively significantly less frequently and we have a lot to do before we can complete a beta 4.
We do need to consistently synchronize on the same structure, given that the synchronize keyword on a method implicitly means synchronize(this).
Re GIL - this follows its purpose, to protect internal data structures in CPython. On the JVM, we simply enjoy a more sophisticated concurrency model.
|
msg8612 (view) |
Author: Santoso Wijaya (santa4nt) |
Date: 2014-06-09.16:11:34 |
|
@zyasoft, I see your point, too. Were we writing this from scratch, I'd probably use Java's already concurrent collections data structures, too (ConcurrentLinkedDeque, especially, is quite elegant with its non-blocking no-lock mechanisms).
But the "thread-safety" doc on `deque` on CPython doc is also a bit misleading, IMHO. It's "thread-safe" in the same sense that `list` is thread-safe, namely its methods are all implemented in C with the GIL guaranteeing its atomicity per function call. If we want to take this "thread-safety" guarantee the correct way for deque, we'd want to do the same for all the built-in collections data structures like list, set, etc.
|
msg8613 (view) |
Author: Jim Baker (zyasoft) |
Date: 2014-06-09.17:24:00 |
|
Santoso, we actually do just that. So dict and set are backed by ConcurrentHashMap, taking advantage of weakly consistent iteration to match CPython semantics; likewise one of the major fixes for 2.5.0 in its beta cycle was for list, see #1026.
The concurrency chapter I wrote for the Jython book is a good place to start, especially these sections:
* http://www.jython.org/jythonbook/en/1.0/Concurrency.html#thread-safety
* http://www.jython.org/jythonbook/en/1.0/Concurrency.html#atomic-operations
The fact that the GIL imposes a memory model is quite relevant to what it actually is supposed to do.
|
msg8614 (view) |
Author: Santoso Wijaya (santa4nt) |
Date: 2014-06-09.17:54:43 |
|
I see. Maybe I'll take a stab at bringing deque and maybe other low-hanging fruits to par, as well.
In the meantime, I think it should be sufficient to fix it functionally for this particular issue.
|
msg8615 (view) |
Author: Santoso Wijaya (santa4nt) |
Date: 2014-06-09.19:12:28 |
|
Patch refresh. All missing methods implemented. All unit tests passed.
|
msg8616 (view) |
Author: Jim Baker (zyasoft) |
Date: 2014-06-09.20:37:53 |
|
Fantastic, just a little bit more work as I mention on the corresponding PR and this should be ready to be merged. Thanks again!
|
msg8621 (view) |
Author: Santoso Wijaya (santa4nt) |
Date: 2014-06-10.16:03:46 |
|
All done.
|
msg8643 (view) |
Author: Jim Baker (zyasoft) |
Date: 2014-06-14.20:47:03 |
|
Fixed in http://hg.python.org/jython/rev/759e56cfcac7
Thanks Santoso!
|
|
Date |
User |
Action |
Args |
2014-06-23 17:52:08 | zyasoft | set | status: pending -> closed |
2014-06-14 20:47:04 | zyasoft | set | status: open -> pending resolution: accepted -> fixed messages:
+ msg8643 |
2014-06-10 16:03:47 | santa4nt | set | messages:
+ msg8621 title: collections.deque constructor does not take keyword arguments -> collections.deque constructor does not take keyword arguments, and missing other 2.7 methods |
2014-06-09 23:22:32 | santa4nt | set | files:
+ issue1949.patch |
2014-06-09 20:37:53 | zyasoft | set | messages:
+ msg8616 |
2014-06-09 19:12:29 | santa4nt | set | files:
+ issue1949.patch messages:
+ msg8615 |
2014-06-09 17:54:43 | santa4nt | set | messages:
+ msg8614 |
2014-06-09 17:24:00 | zyasoft | set | messages:
+ msg8613 |
2014-06-09 16:11:34 | santa4nt | set | messages:
+ msg8612 |
2014-06-09 04:17:36 | zyasoft | set | messages:
+ msg8610 |
2014-06-08 21:08:34 | santa4nt | set | files:
+ issue1949.patch messages:
+ msg8609 |
2014-06-08 19:22:17 | santa4nt | set | messages:
+ msg8608 |
2014-06-08 18:38:00 | santa4nt | set | messages:
+ msg8607 |
2014-06-08 18:26:13 | santa4nt | set | messages:
+ msg8606 |
2014-06-08 18:24:05 | santa4nt | set | files:
+ issue1949.patch messages:
+ msg8605 |
2014-06-08 17:05:07 | zyasoft | set | nosy:
- changeablecore8 |
2014-06-08 17:04:43 | zyasoft | set | messages:
+ msg8604 |
2014-06-08 16:35:08 | santa4nt | set | files:
+ issue1949.patch keywords:
+ patch messages:
+ msg8603 |
2014-06-08 01:15:00 | santa4nt | set | messages:
+ msg8602 |
2014-06-07 18:06:24 | zyasoft | set | messages:
- msg8093 |
2014-06-07 18:06:19 | zyasoft | set | messages:
- msg8092 |
2014-06-07 18:06:13 | zyasoft | set | files:
- sa14-1.html |
2014-06-07 18:06:09 | zyasoft | set | files:
- sa16.html |
2014-06-07 11:40:37 | JonathanFeinberg | set | nosy:
+ JonathanFeinberg |
2014-05-21 23:57:18 | zyasoft | set | resolution: remind -> accepted messages:
+ msg8510 nosy:
+ zyasoft |
2013-08-27 00:11:19 | santa4nt | set | nosy:
+ santa4nt components:
+ Core title: NewInterface -> collections.deque constructor does not take keyword arguments |
2013-08-26 16:25:13 | changeablecore8 | set | files:
+ sa14-1.html messages:
+ msg8093 title: New Interface -> NewInterface |
2013-08-26 16:20:44 | changeablecore8 | set | files:
+ sa16.html nosy:
+ changeablecore8 messages:
+ msg8092 title: deque does not take a maxlen keyword arg -> New Interface |
2013-02-20 00:21:10 | fwierzbicki | set | nosy:
+ fwierzbicki resolution: remind |
2013-02-20 00:20:55 | fwierzbicki | set | priority: high versions:
+ Jython 2.7, - 2.7a2 |
2012-11-27 22:39:11 | irmen | set | nosy:
+ irmen messages:
+ msg7538 |
2012-07-23 22:10:02 | duffy151 | create | |
|