Mon 31 August 2020

Python Deque

This is now my third article on lists. As someone that uses the built-in python list on a fairly regular basis, I might have built up a false sense of security. I'm pretty familiar with these listy-boys. However, recently I found out that I was not thinking about them correctly. Readers might smack themselves if they're familiar with data-structures but don't know how lists are implemented internally. The built-in lists are dynamic arrays.

How else could they optimise a sweet O(1) lookup time on indexing: mylist[4]. Especially when analysts are trying to avoid the built-in iterator and cursing their code with: for i in len(mylist): mylist[i].

Another trait an established data-structurer with be familiar with when it comes to dynamic arrays is that the append and pop methods are an amortised O(1). Amortised; because occasionally you have to suffer a cost of realloc(ating) memory across larger arrays.

Where the list starts to suffer is from poping and inserting at arbitrary positions.

Linked-List

The data-structurer will have had the linked-list slammed into their head often enough that it will pain them to hear about it again. So theory aside, I'll give you that sweet O(1) append and last item pop that you expect from a performant Stack.

Python deque provides a comparatively larger performance hit on initialisation to list and has poor O(n) performance when you want any arbitrary item somewhere in the middle. It does, however, have O(1); popleft, pop, append and appendleft. Due to being a doubly-linked list (or double-ended queue to get the abbreviation deque)

Deque in the wild

I saw a nice little quote from an enginneer on Quora:

In 8 years of getting paid to write computer programs, this post is the only time I’ve typed ‘deque.’

There are many places deque is used in the stdlib, most commonly whenever someone needs a queue or stack such as constructing a traceback, parsing python's sytax tree and keeping track of context scope.

My little run-in with deque was using it instead of a recursive function to avoid python's

maximum recursion depth exceeded

This limit happens to be set to 10^4. The solution was to add child nodes to a deque and when you were done with analysing the current node, popleft the next node.

Python Queue

You might be tempted to ask, well if deque is for queues. What on earth is from queue import Queue.

These queues are different (although, still using deque under the hood). They are optimised for communication across threads, which need to involve locking mechanisms and support methods like put_nowait() and join(). These are not intended to be used as a collective data-structure, hence the lack of support for the in operator.

More information

There is some neat documentation in the cpython repo which contains more data-structures and other alternatives to the standard built-in list. Tools for working with lists

References

Thu 16 April 2020

Module not found Heroku

There are some bugs and problems that give a thrill once they're solved. The best bugs are the ones that teach you something, the worst bugs are the ones that indicate that you've not improved your spelling and the difference between an l and a 1 is large.

Figuring out why I was facing the following traceback in heroku provided a time consuming learning experience, but probably one that I won't forget.

heroku[web.1]: State changed from crashed to starting
heroku[web.1]: State changed from starting to crashed
heroku[web.1]: State changed from crashed to starting
app[web.1]: Traceback (most recent call last):
app[web.1]: File "/home/app/server/bin/server", line 3, in <module>
app[web.1]: from api.server import deploy
app[web.1]: ModuleNotFoundError: No module named 'api'

Why can't the module be found 🤔!

Worst of all, the dockerfile builds locally, and when I run it. It's executing /home/app/server/bin/server and ready to receive traffic...

FROM python:3.8.2

ENV USER appuser
ENV HOME /home/${USER}

RUN mkdir -p ${HOME}/server
WORKDIR ${HOME}/server

ENV PATH ${HOME}/server/bin:${HOME}/.local/bin:$PATH

USER appuser

CMD ["server"]

I won't go into how long I spent on thinking it had something to do with permission. Looking back, it's quite clear that a permission has nothing to do with it, since the logs would say so.

Take a step back

The difference between the image on heroku and the image running locally. What probably made me assume it was a permission error was the quote from their docs:

containers are not run with root privileges in Heroku

So there was some funky business they're doing to the user I provided.

Get closer to the problem

Finding out that I could get inside the heroku container certainly helped me figure out the problem:

heroku run bash

I could now recreate the Module not found error. I tried using pipenv to install the module that was missing, however that didn't work either. hmm.. Where are these modules installed??

Show me the site-packages:

python -m site

Heroku

sys.path = [
    '/',
    '/usr/local/lib/python38.zip',
    '/usr/local/lib/python3.8',
    '/usr/local/lib/python3.8/lib-dynload',
    '/home/appuser/server/.local/lib/python3.8/site-packages',
    '/home/appuser/server',
    '/usr/local/lib/python3.8/site-packages',
]
USER_BASE: '/home/appuser/server/.local' (exists)
USER_SITE: '/home/appuser/server/.local/lib/python3.8/site-packages' (exists)
ENABLE_USER_SITE: True

Local Docker Container

sys.path = [
    '/home/appuser/server',
    '/usr/local/lib/python38.zip',
    '/usr/local/lib/python3.8',
    '/usr/local/lib/python3.8/lib-dynload',
    '/home/hints/.local/lib/python3.8/site-packages',
    '/usr/local/lib/python3.8/site-packages',
]
USER_BASE: '/home/appuser/.local' (exists)
USER_SITE: '/home/appuser/.local/lib/python3.8/site-packages' (exists)
ENABLE_USER_SITE: True

Right so they are not referencing the same site-packages. Are the site packages even installed in the heroku container?!?

$ ls /home/appuser/.local/lib/python3.8/site-packages
Flask-1.1.2.dist-info               mccabe-0.6.1.dist-info
Flask_Alembic-2.0.1.dist-info       mccabe.py
Flask_Cors-3.0.8.dist-info          more_itertools
Flask_JWT_Extended-3.24.1.dist-info more_itertools-8.2.0.dist-info
Flask_SQLAlchemy-2.4.1.dist-info    oauthlib

🎉 so they aren't missing...

Locally

echo $HOME
/home/hints

Heroku

$ echo $HOME
/home/hints/server

Ah.. So $HOME has something to do with it.

Well I have $HOME=/home/appuser and WORKDIR=/home/appuser/server perhaps heroku is setting the work directory to the home directory. 🤷‍♂️

ENV USER hints
ENV HOME /home/${USER}

RUN mkdir -p ${HOME}
WORKDIR ${HOME}

And sure enough fixing my deployment.