Code size report:

   bare-arm:    +0 +0.000% 
minimal x86:    +0 +0.000% 
   unix x64: +1128 +0.137% standard[incl +160(data)]
      stm32:  +360 +0.092% PYBV10
     mimxrt:  +344 +0.095% TEENSY40
        rp2:  +344 +0.103% RPI_PICO
       samd:  +356 +0.134% ADAFRUIT_ITSYBITSY_M4_EXPRESS

Codecov Report

Attention: Patch coverage is 98.52941% with 1 lines in your changes are missing coverage. Please review.

Project coverage is 98.39%. Comparing base (cd8eea2) to head (7dff38f).

@@            Coverage Diff             @@
##           master   #10724      +/-   ##
==========================================
- Coverage   98.39%   98.39%   -0.01%     
==========================================
  Files         161      161              
  Lines       21079    21140      +61     
==========================================
+ Hits        20740    20800      +60     
- Misses        339      340       +1     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

Thanks for the contribution!

This change does add a lot of code size:

   bare-arm:    +0 +0.000% 
minimal x86:    +0 +0.000% 
   unix x64: +1272 +0.162% standard[incl +160(data)]
      stm32:  +496 +0.126% PYBV10
     cc3200:    +0 +0.000% 
    esp8266:  +552 +0.079% GENERIC
      esp32:  +552 +0.036% GENERIC[incl +112(data)]
     mimxrt:  +528 +0.147% TEENSY40
 renesas-ra:  +496 +0.079% RA6M2_EK
        nrf:    +0 +0.000% pca10040
        rp2:  +512 +0.099% PICO
       samd:  +492 +0.184% ADAFRUIT_ITSYBITSY_M4_EXPRESS

It would be good to try and optimise that down. Then we need to make a decision on whether this is an important feature and worth the cost, and/or whether it should be guarded by new config options.

Current code size diff:

   bare-arm:    +0 +0.000% 
minimal x86:    +0 +0.000% 
   unix x64: +1112 +0.141% standard[incl +160(data)]
      stm32:  +372 +0.095% PYBV10
     cc3200:    +0 +0.000% 
    esp8266:  +432 +0.062% GENERIC
      esp32:  +416 +0.027% GENERIC[incl +80(data)]
     mimxrt:  +376 +0.106% TEENSY40
 renesas-ra:  +376 +0.060% RA6M2_EK
        nrf:    +0 +0.000% pca10040
        rp2:  +392 +0.121% PICO
       samd:  +360 +0.134% ADAFRUIT_ITSYBITSY_M4_EXPRESS

I was thinking perhaps these new features should only be enabled on larger devices, but looking at:

Looking at this again, I did some code-size measurements with various parts in this PR disabled (on stm32 PYBv1.0 which is indicative of most bare-metal ports size):

• without iteration, without subscript: +228 bytes
• without iteration: +296 bytes
• without subscript: +296 bytes
• the full PR: +364 bytes

I think iteration and subscript are less important/useful than the additional double-ended methods (appendleft and pop) and so can be gated by additional options that are enabled at higher feature levels.

So I'd propose to add the options:

• MICROPY_PY_COLLECTIONS_DEQUE_ITER
• MICROPY_PY_COLLECTIONS_DEQUE_SUBSCR

And have these default to MICROPY_CONFIG_ROM_LEVEL_AT_LEAST_FULL_FEATURES.

Reducing the default config size by a third sounds reasonable for sure.

Out of interest @LordFlashmeow did you have a particular use-case using iter and indexing?
My personal use of deque is to implement Queue so I don't particularly need these features myself, I'm curious if you are actively using them?

Out of interest @LordFlashmeow did you have a particular use-case using iter and indexing? My personal use of deque is to implement Queue so I don't particularly need these features myself, I'm curious if you are actively using them?

I’m not actively using them, but supporting iter matches the reference implementation and makes it work with lots of built-in python functions.

Indexing isn’t strictly necessary, but I think it’s natural to have and brings the behavior more in-line with the reference implementation.

Also, curious what's the use case for .extend(), and related, initialising with an existing iterable? (both added in this PR)

In case it helps with this discussion, I have an application for which I need to implement a fast moving average of data acquired from a sensor. Doing this with a performant deque would be ideal, and much cleaner to implement if the deque is iterable. If selecting just a subset of the added functionality LordFlashmeow has implemented is necessary due to space constraints, I would like to log my vote for making deque iterable as that would be very helpful.

@SAK917 Have you considered a ringbuf in this application? It has the potential to be more efficient because the storage can be in a fixed-size pre-allocated object such as an array.

Thanks for your suggestion @peterhinch, I appreciate you taking the time to respond and agree that a ring buffer / circular queue makes sense for my application. That said, my understanding of the MP deque is that it is implemented as a performant statically allocated ring buffer, and as far as that aspect it works well now. However, in addition to this PR bringing the MP deque closer to feature parity with CPython, if the deque was just iterable without the other new functionality, it would make a moving average much easier to implement:

deq = collections.deque((), size)
while true:
    deq.append(sensor.data())
    moving_average = sum(deq) / len(deq)

And I do recognize that there is a moving average workaround for the current non-iterable deque implementation (psuedocode below) that is also more performant than calculating the sum every time the moving average is updated as the example above does:

deq = collections.deque((), size)
sum = 0 
count = 0

while true:
  value = sensor.data()
  deq.append(value)
  sum += value
  count += 1

  if count > size:
    sum -= deq.popleft()
    count -= 1

  moving_average = sum / count

But this is unintuitive and the iterable deque implementation above is considerably clearer and more concise, especially for novice / non-programmers that expect the MP deque to function similarly to the CPython implementation.

This is an automated heads-up that we've just merged a Pull Request
that removes the STATIC macro from MicroPython's C API.

See #13763

A search suggests this PR might apply the STATIC macro to some C code. If it
does, then next time you rebase the PR (or merge from master) then you should
please replace all the STATIC keywords with static.

Although this is an automated message, feel free to @-reply to me directly if
you have any questions about this.

I have rebased this PR, fixed conflicts, and make STATIC lowercase. I also added the two configuration options for iteration and subscription as mentioned above, although I enabled them by default at the EXTRA features level (same level that collections.deque is enabled) because they don't cost much more (about +70 bytes each on Cortex-M targets).

Current size code change for this PR:

   bare-arm:    +0 +0.000% 
minimal x86:    +0 +0.000% 
   unix x64: +1128 +0.138% standard[incl +160(data)]
      stm32:  +372 +0.096% PYBV10
     cc3200:    +0 +0.000% 
    esp8266:  +452 +0.065% ESP8266_GENERIC
      esp32:  +464 +0.027% ESP32_GENERIC[incl +72(data)]
     mimxrt:  +336 +0.093% TEENSY40
 renesas-ra:  +368 +0.059% EK_RA6M2
        nrf:    +0 +0.000% PCA10040
        rp2:  +320 +0.097% RPI_PICO
       samd:  +344 +0.131% ADAFRUIT_ITSYBITSY_M4_EXPRESS

Now merged. Thanks @LordFlashmeow for the implementation.

Thank you @LordFlashmeow, this is very helpful!