32 bit integer logic in Viper?

[peterhinch]

This is of academic interest as I've achieved adequate speed, but I keep wondering if improvement is possible.

The requirement is to move data from one bytearray to another, performing inversion (1's complement) in the process. The first go was

# 898/453us for 2000 bytes (125/250MHz) on Pico
@micropython.viper
def foo(dest:ptr8, source:ptr8, length:int):
    for n in range(length):
        c = source[n]
        dest[n] = c ^ 0xFF

followed by:

# 483/241 us for 2000 bytes
@micropython.viper
def bar(dest:ptr16, source:ptr16, length:int):
    for n in range(length):
        c: uint = source[n]
        dest[n] = c ^ 0xFFFF

Extension to 32 bits founders because unsigned integers >0x3FFFFFFF become long ints. Any clever fixes (aside from C/asm)?

[GitHubsSilverBullet]

@micropython.viper
def inv32_a(dest:ptr32, source:ptr32, length:int):
    n: int = 0
    z: int = -1
    for n in range(length):
        dest[n] = source[n] ^ z

@micropython.viper
def inv32_b(dest:ptr32, source:ptr32, length:int):
    n: int = length-1
    z: int = -1
    while n >= 0:
        dest[n] = source[n] ^ z
        n -= 1

N = 2000
src = bytearray(0xe7 for _ in range(N))

for b in src[0:8]:
    print(f'{b:08b}', end=' ')
print()

dst = bytearray(0 for _ in range(N))
t0 = time.ticks_us()
inv32_a(dst, src, N>>2)
t1 = time.ticks_us()
for b in dst[0:8]:
    print(f'{b:08b}', end=' ')
print(f'\n{time.ticks_diff(t1,t0)}')

dst = bytearray(0 for _ in range(N))
t0 = time.ticks_us()
inv32_b(dst, src, N>>2)
t1 = time.ticks_us()
for b in dst[0:8]:
    print(f'{b:08b}', end=' ')
print(f'\n{time.ticks_diff(t1,t0)}')

Give those a try…

[GitHubsSilverBullet]

Oh, one more thing… If you want to be really fast, I mean really really fast (and waste only a few CPU cycles), setup a statemachine.
The PIO asm reads from fifo, inverts and writes to fifo. Then setup two DMA channels. Fire and forget.

[GitHubsSilverBullet]

@micropython.asm_thumb
def inv32_c(r0, r1, r2):
    # r0: ptr32 dst
    # r1: ptr32 src
    # r2: uint32 length
    # r4: transfer
    # r5: 0xffffffff
    mov(r5, 0)
    mvn(r5,r5)
    label(loop)
    ldr(r4, [r1, 0])
    eor(r4, r5)
    str(r4, [r0, 0])
    add(r0, 4)
    add(r1, 4)
    sub(r2, r2, 1)
    bne(loop)

I have to admit, I do like this one. Two and a half times faster than the fastest Viper code…

[GuillaumeLeclerc]

Just out of curiosity, how would you do inversion in PIO which doesn't have an ALU. I'm sure it's possible I just wonder.

[rkompass]

By mov(x, invert(x)) or mov(osr, invert(isr)).
The docs are here: https://docs.micropython.org/en/latest/library/rp2.html, which were created by Peter iirc.

[peterhinch]

Thank you. I can't use the PIO as the code is meant to be cross-platform. But I would like to know why my solution fails:

@micropython.viper
def foo(dest:ptr32, source:ptr32, length:int):
    d :uint32 = 0xFFFFFFFF
    for n in range(length):
        c: uint32 = source[n]
        dest[n] = c ^ d  # ViperTypeError: can't do binary op between 'int' and 'object'

Applying elements of your working code one by one, the line that fixes it is here:

@micropython.viper
def foo(dest:ptr32, source:ptr32, length:int):
    d : int = -1  # This fixes it. Also works if I declare uint32 but setting a uint negative is ugly
    for n in range(length):
        c: uint32 = source[n]
        dest[n] = c ^ d

This fact that failure occurs when I use d seems to imply that my

 d :uint32 = 0xFFFFFFFF

creates a long int in the teeth of the declaration. Any thoughts? Bug?

[GitHubsSilverBullet]

inv: uint = int(0xffffffff)

That works as well. And it ›feels‹ more natural to do bit mangling on an unsigned type.
Though I do not believe that it makes any difference internally (within Viper code).

As far as I remember, regular MicroPython integers have a limited range(31bits? maybe 30bits?)
And it looks like within Viper code an integer/unsigned integer really has 32bits. The magic lies in the conversion from object to (true)integer which int() apparently does.

Don't think it's a bug, more like implementation specific behavior.

PS. If you replace the »for … in range()« with a simple »while« and do the counting manually, it shaves off quite some additional cycles.

[rkompass]

Last year I raised an issue for that: #9114.
Indeed, wrapping the value with int() seems to be a viable workaround.

[peterhinch]

@GitHubsSilverBullet Thank you for the insights into while and int().
@rkompass I'll add a note to your issue as I think the behaviour is confusing. In my view it's reasonable to expect the line

d :uint32 = 0xFFFFFFFF

either to produce a uint32 or to fail because 0xFFFFFFFF is a long int. In practice it produces a long int causing a later failure.

[rkompass]

@GitHubsSilverBullet @peterhinch @GuillaumeLeclerc
The PIO idea had to be tried, partly because I have the rp2 DMA class available.
Results with 10000 bytes / 2500 32bit integers:

11100111 11100111 11100111 11100111 11100111 11100111 11100111 11100111 

00011000 00011000 00011000 00011000 00011000 00011000 00011000 00011000 
00011000 00011000 00011000 00011000 00011000 00011000 00011000 00011000 
91 us  # <---- inversion with PIO/DMA at 125 MHz


11100111 11100111 11100111 11100111 11100111 11100111 11100111 11100111 

00011000 00011000 00011000 00011000 00011000 00011000 00011000 00011000 
1280 us  # <---- inversion with viper function a at 125 MHz
00011000 00011000 00011000 00011000 00011000 00011000 00011000 00011000 
1070 us  # <---- inversion with viper function b at 125 MHz
00011000 00011000 00011000 00011000 00011000 00011000 00011000 00011000 
277 us  # <---- inversion with assembler function at 125 MHz

I gratefully used and modified @GitHubsSilverBullet s code.
Which is here:

import time

@micropython.viper
def inv32_a(dest:ptr32, source:ptr32, length:int):
    z: uint = uint(0xFFFFFFFF)
    for n in range(length):
        dest[n] = source[n] ^ z

@micropython.viper
def inv32_b(dest:ptr32, source:ptr32, length:int):
    n: uint = length-1
    z: uint = uint(0xFFFFFFFF)
    while n >= 0:
        dest[n] = source[n] ^ z
        n -= 1

@micropython.asm_thumb
def inv32_c(r0, r1, r2): # r0: ptr32 dst, r1: ptr32 src, r2: uint32 length
    mov(r5, 0)           # r4: transfer, r5: 0xffffffff
    mvn(r5,r5)
    label(loop)
    ldr(r4, [r1, 0])
    eor(r4, r5)
    str(r4, [r0, 0])
    add(r0, 4)
    add(r1, 4)
    sub(r2, r2, 1)
    bne(loop)

from rp2 import PIO, StateMachine, asm_pio
from rp2_dma import RP2_Dma
from array import array

#  PIO program that pulls from the TX FIFO, inverts and pushes to the RX FIFO.
@asm_pio(pull_thresh=32, push_thresh=32)
def pio_inout():
    pull(block)            # from TX FIFO to OSR
    mov(isr, invert(osr))  # from OSR inverted to ISR
    push(block)            # from ISR to RX FIFO

#  Setup a PIO state machine with that program and activate it
sm = rp2.StateMachine(0, pio_inout, freq=125_000_000)
sm.active(1)


N = 2500
src = array('I', 0xe7e7e7e7 for _ in range(N))
for i in src[0:2]:
    print(f'{i & 0xff:08b}', end=' ')
    print(f'{(i>>8) & 0xff:08b}', end=' ')
    print(f'{(i>>16) & 0xff:08b}', end=' ')
    print(f'{(i>>24) & 0xff:08b}', end=' ')
print('\n')
dst = array('I', 0 for _ in range(N))

dma_src = RP2_Dma(src, sm)  # We need 2 DMA channels working: from source to TX FIFO
dma_dst = RP2_Dma(sm, dst)  #    and from RX FIFO to destination.
dma_dst.start()             # The second may start, it synchronizes anyway.
t0 = time.ticks_us()
dma_src.start()             # Start from source to TX FIFO
while dma_dst.busy():       #    and measure timing when from RX FIFO to destination is finished.
    t1 = time.ticks_us()

for i in dst[0:2]:
    print(f'{i & 0xff:08b}', end=' ')
    print(f'{(i>>8) & 0xff:08b}', end=' ')
    print(f'{(i>>16) & 0xff:08b}', end=' ')
    print(f'{(i>>24) & 0xff:08b}', end=' ')
print()
for i in dst[2498:2500]:
    print(f'{i & 0xff:08b}', end=' ')
    print(f'{(i>>8) & 0xff:08b}', end=' ')
    print(f'{(i>>16) & 0xff:08b}', end=' ')
    print(f'{(i>>24) & 0xff:08b}', end=' ')
print(f'\n{time.ticks_diff(t1,t0)} us')

print('\n')

N = 10000
src = bytearray(0xe7 for _ in range(N))
for b in src[0:8]:
    print(f'{b:08b}', end=' ')
print('\n')

dst = bytearray(0 for _ in range(N))
t0 = time.ticks_us()
inv32_a(dst, src, N>>2)
t1 = time.ticks_us()
for b in dst[0:8]:
    print(f'{b:08b}', end=' ')
print(f'\n{time.ticks_diff(t1,t0)} us')

dst = bytearray(0 for _ in range(N))
t0 = time.ticks_us()
inv32_b(dst, src, N>>2)
t1 = time.ticks_us()
for b in dst[0:8]:
    print(f'{b:08b}', end=' ')
print(f'\n{time.ticks_diff(t1,t0)} us')

dst = bytearray(0 for _ in range(N))
t0 = time.ticks_us()
inv32_c(dst, src, N>>2)
t1 = time.ticks_us()
for b in dst[0:8]:
    print(f'{b:08b}', end=' ')
print(f'\n{time.ticks_diff(t1,t0)} us')

The assembler is 4 times faster than the fastest viper function.
The PIO/DMA combo is 3 times faster than the assembler.

[GitHubsSilverBullet]

Very nice indeed. As soon as there are bigger datablocks to move (or quite often), the advantage will be even more visible.

[peterhinch]

Amazing performance.

[GuillaumeLeclerc]

Nice! I didn't know there was an invert modifier that's good to know!

…

On Sat, Apr 15, 2023, 1:48 PM rkompass ***@***.***> wrote: By mov(x, invert(x)) or mov(osr, invert(isr)). The docs are here: https://docs.micropython.org/en/latest/library/rp2.html, which were created by Peter iirc. — Reply to this email directly, view it on GitHub <#11259 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAPMOGZE7744ATTYWMMBFLDXBLNNXANCNFSM6AAAAAAW6LSZNY> . You are receiving this because you commented.Message ID: ***@***.*** com>