Dynamic Arrays in Vyper

A simple library for ~~swerving~~ past a restriction of an otherwise powerful language.

by Kenny Peluso

Source: https://www.flickr.com/photos/parkourdude45/8339193840

Vyper does not allow for dynamic arrays

so says the frequently changing Vyper docs as of 2/8/19. This can be a pain.

I made a small library that ~~swerves~~ past this restriction. We’ll discuss that in a moment. I’ll briefly review Vyper before analyzing the library.

Source: https://cdn-images-1.medium.com/max/2000/1*bgBCdx65C6_w6XztyRXfYg.png

Vyper

is a language built to interact with smart contracts on Ethereum. According to Vitalik:

Vyper is a contract-oriented, pythonic programming language that targets the Ethereum Virtual Machine (EVM)

You can read the Vyper docs here and play with it in a Remix-like, in-browser environment here.

The Becoming Future team loves Vyper for all the simplicity and security it provides. We hope to contribute more to the (admittedly, currently tiny) Vyper community in the future.

Library

Let’s now dive into a simplified version of my implementation. Checkout and fork the repo here! I made implementations for dynamic arrays of different data types supported by Vyper. They all follow the same format, so if you understand one, you understand them all. We’ll be focusing on a simplified version of the uint256 dynamic array implementation in this post.

MAXVAL: constant(uint256) = 2**255
ls: map(uint256, uint256)
currMax: public(uint256)
@public
@constant
def get(_idx: uint256) -> uint256:
    assert _idx < self.currMax
    return self.ls[_idx]
@public
@constant
def length() -> uint256:
    return self.currMax
@public
def set(_idx: uint256, _val: uint256):
    self.ls[_idx] = _val
@public
def append(_val: uint256):
    self.set(self.currMax, _val)
    self.currMax += 1
@public
def detach():
    assert self.currMax > 0
    self.currMax -= 1
@public
def remove(_idx: uint256):
    assert self.currMax > 0
    assert self.currMax > _idx
    i: uint256
    for not_i in range(MAXVAL):
        i = convert(not_i, uint256)
        if i == self.currMax - 1:
            self.currMax -= 1
            return
        elif i >= _idx and i < self.currMax - 1:
            self.set(i, self.get(i + 1))

Here’s why this simple code is useful: Vyper only allows you to perform range() on a constant-sized input, which is problematic when one has a dynamic amount of content to loop over. Operations such as remove() would be impossible without a tiny fix. Simply define a different, mutable variable (in this case, self.currMax) and loop along range(MAX) until self.currMax is reached.

That’s it!

I chose MAX to be the largest value a uint256 could be in Vyper, namely 2²⁵⁶ just because I can. Clearly this destroys my space complexity, but at least all use cases are permitted. Feel free to alter this value to fit your own needs.

I would not use the above implementation in production. I’d use the actual implementation instead i.e. my library (found in the linked repo above and below and here). The actual implementation, my library, houses many security checks including whitelisted lists, which prevent a random person from accidentally or purposefully overriding your data.

Checkout and fork the repo here!

Analysis

+----------------------+-------------+---------------+-----------+
|       Feature        |    Array    | Dynamic Array |  My Array |
+----------------------+-------------+---------------+-----------+
| Indexing             |     O(1)    |     O(1)      |    O(1)   |
| Insert/delete @ start|     O(n)    |     O(n)      |    O(1)   |
| Insert/delete @ end  |     O(1)    | O(n) amortized|    O(1)   |
| Insert/delete @ mid  |     O(n)    |     O(n)      |    O(1)   |
| Wasted space         |      0      |     O(n)      |    O(M)   |
+----------------------+-------------+---------------+-----------+
where M := 2^256 (but you can tune this to your liking)

(Source: https://en.wikipedia.org/wiki/Dynamic_array)

(Source: https://stackoverflow.com/questions/53939725/why-is-deletion-of-an-item-at-end-of-dynamic-array-on-time-complexity)

Thanks for reading! Feedback is always welcomed!