Issue1949

classification
Title: collections.deque constructor does not take keyword arguments, and missing other 2.7 methods
Type: behaviour Severity: normal
Components: Core Versions: Jython 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: JonathanFeinberg, duffy151, fwierzbicki, irmen, santa4nt, zyasoft
Priority: high Keywords: patch

Created on 2012-07-23.22:10:02 by duffy151, last changed 2014-06-23.17:52:08 by zyasoft.

Files
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.
Messages
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!
History
Date User Action Args
2014-06-23 17:52:08zyasoftsetstatus: pending -> closed
2014-06-14 20:47:04zyasoftsetstatus: open -> pending
resolution: accepted -> fixed
messages: + msg8643
2014-06-10 16:03:47santa4ntsetmessages: + 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:32santa4ntsetfiles: + issue1949.patch
2014-06-09 20:37:53zyasoftsetmessages: + msg8616
2014-06-09 19:12:29santa4ntsetfiles: + issue1949.patch
messages: + msg8615
2014-06-09 17:54:43santa4ntsetmessages: + msg8614
2014-06-09 17:24:00zyasoftsetmessages: + msg8613
2014-06-09 16:11:34santa4ntsetmessages: + msg8612
2014-06-09 04:17:36zyasoftsetmessages: + msg8610
2014-06-08 21:08:34santa4ntsetfiles: + issue1949.patch
messages: + msg8609
2014-06-08 19:22:17santa4ntsetmessages: + msg8608
2014-06-08 18:38:00santa4ntsetmessages: + msg8607
2014-06-08 18:26:13santa4ntsetmessages: + msg8606
2014-06-08 18:24:05santa4ntsetfiles: + issue1949.patch
messages: + msg8605
2014-06-08 17:05:07zyasoftsetnosy: - changeablecore8
2014-06-08 17:04:43zyasoftsetmessages: + msg8604
2014-06-08 16:35:08santa4ntsetfiles: + issue1949.patch
keywords: + patch
messages: + msg8603
2014-06-08 01:15:00santa4ntsetmessages: + msg8602
2014-06-07 18:06:24zyasoftsetmessages: - msg8093
2014-06-07 18:06:19zyasoftsetmessages: - msg8092
2014-06-07 18:06:13zyasoftsetfiles: - sa14-1.html
2014-06-07 18:06:09zyasoftsetfiles: - sa16.html
2014-06-07 11:40:37JonathanFeinbergsetnosy: + JonathanFeinberg
2014-05-21 23:57:18zyasoftsetresolution: remind -> accepted
messages: + msg8510
nosy: + zyasoft
2013-08-27 00:11:19santa4ntsetnosy: + santa4nt
components: + Core
title: NewInterface -> collections.deque constructor does not take keyword arguments
2013-08-26 16:25:13changeablecore8setfiles: + sa14-1.html
messages: + msg8093
title: New Interface -> NewInterface
2013-08-26 16:20:44changeablecore8setfiles: + sa16.html
nosy: + changeablecore8
messages: + msg8092
title: deque does not take a maxlen keyword arg -> New Interface
2013-02-20 00:21:10fwierzbickisetnosy: + fwierzbicki
resolution: remind
2013-02-20 00:20:55fwierzbickisetpriority: high
versions: + Jython 2.7, - 2.7a2
2012-11-27 22:39:11irmensetnosy: + irmen
messages: + msg7538
2012-07-23 22:10:02duffy151create