Comparing `array` vs `bytearray` in performance

array vs bytearray.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "54ee938c-dfc2-49f6-ba56-1b48c29081e9",
   "metadata": {},
   "source": [
    "# Comparing `array` vs. `bytearray`\n",
    "\n",
    "I was using `array(\"B\", [...])` to store and a manipulate a small, indexed bitmap image, but then I realized that I might want to use `bytearray` instead. I will test the two alternatives based on:\n",
    "\n",
    " - memory usage\n",
    " - performance of certain operations\n",
    "\n",
    "Let's start by importing everything:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "430937ea-ce06-4992-9135-51caa2bf22ee",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "from array import array\n",
    "from io import BytesIO\n",
    "from random import randrange\n",
    "\n",
    "import numpy as np\n",
    "import png"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e324679e-c3ea-48f2-bf89-d7c5055a9f93",
   "metadata": {},
   "source": [
    "Some constants that I was using:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "f530dbe9-86c3-418d-a611-6eb63a6f92cb",
   "metadata": {},
   "outputs": [],
   "source": [
    "WIDTH = 80\n",
    "HEIGHT = 45\n",
    "N_BYTES = WIDTH * HEIGHT\n",
    "\n",
    "PALETTE = [\n",
    "    (0xFF, 0xFF, 0xFF),\n",
    "    (0x19, 0x19, 0x19),\n",
    "    (0xEB, 0x55, 0x29),\n",
    "    (0xF2, 0xAC, 0x00),\n",
    "    (0xF9, 0xD7, 0x58),\n",
    "    (0x5A, 0xC7, 0x5C),\n",
    "    (0x50, 0x8E, 0xE3),\n",
    "    (0xA7, 0x50, 0xBA),\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f017fb1-cf38-475e-87fa-ddaeb3b8fabd",
   "metadata": {},
   "source": [
    "Define the `array` (`a`) and the `bytearray` (`b`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "bf86df8a-aa59-4f9a-b993-7ecfd8af9290",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = array(\"B\", (0 for _ in range(N_BYTES)))\n",
    "b = bytearray(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4459b018-771e-4eff-a52c-fd1defc1242a",
   "metadata": {},
   "source": [
    "# Size comparison\n",
    "\n",
    "Let's compare how many bytes are required to store the base Python object. Both `array` and `bytearray` are types that have a \"length\", so they will store that inline in the [`PyVarObject`](https://docs.python.org/3/c-api/structures.html#c.PyVarObject) struct.\n",
    "\n",
    "Thus, on a machine with 64 bit pointers, the size of the object should be:\n",
    "\n",
    " - 8 bytes for the [`PyType*`](https://docs.python.org/3/c-api/structures.html#c.Py_TYPE) pointer\n",
    " - 8 bytes for the `Py_ssize_t` containing the [`Py_REFCNT`](https://docs.python.org/3/c-api/structures.html#c.Py_REFCNT)\n",
    " - 8 bytes for the `Py_ssize_t` containing the [`ob_size`](https://docs.python.org/3/c-api/structures.html#c.Py_SIZE) field.\n",
    "\n",
    "Anything bytes other than this are overhead. Note: both will need at least one pointer (8 bytes) to point to the actual memory containing the bytes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "71436ac4-1963-4c18-98d7-2f5226c275f5",
   "metadata": {},
   "outputs": [],
   "source": [
    "MINIMUM_OVERHEAD = 3 *8 "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "194679fa-6a16-4a39-9d2b-7f9b596a9336",
   "metadata": {},
   "source": [
    "What is the size of the `array`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a3cad8fd-4617-43a1-ba99-6834f98d674a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3828"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sys.getsizeof(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "780083d3-2884-4483-b793-1c3984384def",
   "metadata": {},
   "source": [
    "And how much of that is pure overhead?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "2f8863ed-8f73-4751-8fe4-f56123748dcf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "204"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sys.getsizeof(a) - N_BYTES - MINIMUM_OVERHEAD"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d6800ed-9378-423a-bf29-9fb8950e7727",
   "metadata": {},
   "source": [
    "That's a lot more than I expected. I looked at the [source code](https://github.com/python/cpython/blob/v3.11.4/Modules/arraymodule.c#L30-L39) for the array module in Python 3.11.4, and `array` is more complicated than I imagined. Here's its struct:\n",
    "\n",
    "```c\n",
    "typedef struct arrayobject {\n",
    "    PyObject_VAR_HEAD\n",
    "    char *ob_item;\n",
    "    Py_ssize_t allocated;\n",
    "    const struct arraydescr *ob_descr;\n",
    "    PyObject *weakreflist; /* List of weak references */\n",
    "    Py_ssize_t ob_exports;  /* Number of exported buffers */\n",
    "} arrayobject;\n",
    "```\n",
    "\n",
    "5 more 64-bit words in this struct alone, plus the actual items behind te `ob_item` pointer, and \"description\" (what the type code `B` means) requires indirection into a static table. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "379fed51-8fb6-48a7-9bf5-ad593cb44397",
   "metadata": {},
   "source": [
    "How about `bytearray`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "72de50cf-2b76-4aa7-b7c0-9cbf05e84e54",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3657"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sys.getsizeof(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06b5f20b-77e6-495e-a188-28934269b30e",
   "metadata": {},
   "source": [
    "How much is overhead?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "f69cf614-ae5f-4c30-a345-63749f616a20",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "33"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sys.getsizeof(b) - N_BYTES - MINIMUM_OVERHEAD"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ab00437-36e4-420d-985a-1ee11cb57dbf",
   "metadata": {},
   "source": [
    "That's much better!\n",
    "\n",
    "Let's peer into [its definition](https://github.com/python/cpython/blob/main/Include/cpython/bytearrayobject.h#L6-L12):\n",
    "\n",
    "```c\n",
    "typedef struct {\n",
    "    PyObject_VAR_HEAD\n",
    "    Py_ssize_t ob_alloc;   /* How many bytes allocated in ob_bytes */\n",
    "    char *ob_bytes;        /* Physical backing buffer */\n",
    "    char *ob_start;        /* Logical start inside ob_bytes */\n",
    "    Py_ssize_t ob_exports; /* How many buffer exports */\n",
    "} PyByteArrayObject;\n",
    "```\n",
    "\n",
    "4 64-bit words in this struct, but no indirection for typecodes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "227b88c8-e39e-40cb-8726-fdd3f277457b",
   "metadata": {},
   "source": [
    "## Verdict\n",
    "\n",
    "`bytesarray` is a smaller object, with less overhead."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "002d6ab6-6b86-4692-86cf-499ed714945d",
   "metadata": {},
   "source": [
    "# Performance"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a876c27-5b8e-40cf-8327-01cdd48b49a0",
   "metadata": {},
   "source": [
    "One operation I need is to set arbitrary values in the array. Let's see how long that takes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "44d9868c-7bfd-4fa4-8054-929d95215fa7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30 ns ± 0.114 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit a[0] = 255"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "02621383-7cf4-49e9-87a1-faf45ac7e1f1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16.9 ns ± 0.0911 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit b[0] = 255"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48fc60f9-552c-4b8f-b371-ca5d5f38ff79",
   "metadata": {},
   "source": [
    "It seems that `bytesarray` is unambigously the faster of the two. But this is only for setting the first element of the array. How about anywhere in the array? Will we see any cache effects for arrays that are only 3600 bytes?\n",
    "\n",
    "First, since I will be using `randrange`, let's callibrate its speed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "4495e389-27ba-46ae-9c6a-6088e229d7fe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "151 ns ± 0.619 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit randrange(255)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "714cbea3-9250-48d4-b50a-ac4679f072e6",
   "metadata": {},
   "source": [
    "Dang, randrange is slow! Okay, let's keep that in mind while we set random elements in arrays."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "4be9de4c-44fc-49c1-93b4-2409b3a8c07f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "194 ns ± 1.18 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit a[randrange(N_BYTES)] = 255"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "a9b147fc-9026-4877-a16d-2f888941a84e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "176 ns ± 0.856 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit b[randrange(N_BYTES)] = 255"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4650b4f4-332e-447d-9db5-d188cb6b2105",
   "metadata": {},
   "source": [
    "I'll roughly remove the overhead that `randrange()` added:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "769cc61b-9b21-4da3-bcad-0d2350630c59",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(40.82, 43.18)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tuple(194 - 152 + s * 1.18 for s in (-1, 1))   # array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "d76c8716-5a6a-46d3-bf06-2302f286a795",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(23.144, 24.856)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tuple(176 - 152 + s * 0.856 for s in (-1, 1))  # bytearray"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1fbc1198-b6d7-457f-a35f-88c8367cb463",
   "metadata": {},
   "source": [
    "`bytearray` still does better here, nearly halving the time taken."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1ec6b85-148d-46f1-b9ea-9afb2206dad5",
   "metadata": {},
   "source": [
    "## My actual use case\n",
    "\n",
    "My use case is converting the bytes into a `.png` image using the [`pypng` library](https://pypi.org/project/pypng/).\n",
    "\n",
    "To do that, I use the following method to convert to the bytes of a PNG image:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "39892d04-cf8a-4fc1-ab6a-9fae7281e3cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_png(data, width=WIDTH, height=HEIGHT, palette=PALETTE, _png=png):\n",
    "    png_writer = _png.Writer(width, height, palette=palette, bitdepth=8)\n",
    "    with BytesIO() as f:\n",
    "        png_writer.write_array(f, data)\n",
    "        return f.getvalue()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1aaa046c-ee2e-4259-b057-901b449aa644",
   "metadata": {},
   "source": [
    "How long does it take to convert an `array` into a PNG?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "2bf178e4-3fbb-4b91-bdee-63c7745ba0c8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "34.2 µs ± 1.05 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit to_png(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bef725ce-e9e1-4512-8db2-0bc524182473",
   "metadata": {},
   "source": [
    "How about `bytearray`?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "034daefc-08c9-468f-9df6-e4d65f804063",
   "metadata": {},
   "source": [
    "It's a matter of a less than microsecond (one one-millionth of a second), but `bytearray` wins. Not that I think that one microsecond is significant in the long run!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41cd4ed0-69c3-4cce-9345-d9fbc7054891",
   "metadata": {},
   "source": [
    "# Stray thoughts\n",
    "\n",
    "Both `bytesarray` and `array` implement the [buffer protocol](https://docs.python.org/3/c-api/buffer.html#bufferobjects) which is why both have a field called `ob_exports` that is incremented every time a consumer (such as a C extension library) calls [`PyObject_GetBuffer`](https://docs.python.org/3/c-api/buffer.html#c.PyObject_GetBuffer)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "db8992fa-b8aa-4bf0-aeba-81ac067d45cb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "33.7 µs ± 148 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit to_png(b)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}