Issue1949

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)
>>>

I'm encountering this problem as well.

Target beta 4

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.

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.

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.

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.

@zyasoft. Why not keep the current doubly-linked nodes implementation and simply synchronize the methods we expose?

@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.

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.

Another patch refresh. Passes all but 1 test in lib/2.7/test/test_deque.py (due to an unimplemented deque.reverse() method).

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.

@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.

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.

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.

Patch refresh. All missing methods implemented. All unit tests passed.

Fantastic, just a little bit more work as I mention on the corresponding PR and this should be ready to be merged. Thanks again!

All done.

Fixed in http://hg.python.org/jython/rev/759e56cfcac7

Thanks Santoso!