32 bit integer logic in Viper? #11259

peterhinch · 2023-04-14T12:33:02Z

peterhinch
Apr 14, 2023
Collaborator

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 · 2023-04-14T14:20:25Z

GitHubsSilverBullet
Apr 14, 2023

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

4 replies

GitHubsSilverBullet Apr 14, 2023

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 Apr 14, 2023

@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 Apr 15, 2023

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 Apr 15, 2023

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 · 2023-04-15T06:59:25Z

peterhinch
Apr 15, 2023
Collaborator Author

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?

3 replies

GitHubsSilverBullet Apr 15, 2023

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 Apr 15, 2023

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

peterhinch Apr 16, 2023
Collaborator Author

@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 · 2023-04-15T19:11:14Z

rkompass
Apr 15, 2023

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

2 replies

GitHubsSilverBullet Apr 15, 2023

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

peterhinch Apr 16, 2023
Collaborator Author

Amazing performance.

GuillaumeLeclerc · 2023-04-15T21:55:03Z

GuillaumeLeclerc
Apr 15, 2023

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>

0 replies

32 bit integer logic in Viper? #11259

Uh oh!

peterhinch Apr 14, 2023 Collaborator

Replies: 4 comments · 9 replies

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

peterhinch Apr 15, 2023 Collaborator Author

Uh oh!

Uh oh!

Uh oh!

Uh oh!

peterhinch Apr 16, 2023 Collaborator Author

Uh oh!

Uh oh!

Uh oh!

peterhinch Apr 16, 2023 Collaborator Author

Uh oh!

peterhinch
Apr 14, 2023
Collaborator

Replies: 4 comments 9 replies

peterhinch
Apr 15, 2023
Collaborator Author

peterhinch Apr 16, 2023
Collaborator Author

peterhinch Apr 16, 2023
Collaborator Author