pyrsistent_perf.py

from pyrsistent import pvector, pdeque, psequence
from collections import deque, defaultdict

import time
import inspect
import itertools
import functools
import asyncio

import matplotlib.pyplot as plt

def trace(*args, **kwargs):
	print(*args, **kwargs)
	return args[-1]

cache = defaultdict(dict)

def generate(what, size):
	if size not in cache[what]:
		value = what(range(size))
		cache[what][size] = value
		return value
	value = cache[what][size]
	if len(value) > size:
		try:
			del value[size:]
		except TypeError:
			while len(value) > size:
				value.pop()
	elif len(value) < size:
		value += range(len(value), size)
	return value

async def timeit_task(times, stmt, setup=lambda *args: args, largs=tuple(), repeat=2000):
	for _ in range(repeat):
		try:
			args = setup(*largs)
			starttime = time.perf_counter()
			stmt(*args)
			endtime = time.perf_counter()
			times.append(endtime - starttime)
		except Exception as err:
			trace(err, end=' ', flush=True)
			times[:] = [float('infinity')]
			return
		await asyncio.sleep(0)

async def timeit(*args, timeout=60, **kwargs):
	times = []
	try:
		await asyncio.wait_for(
			asyncio.create_task(timeit_task(times, *args, **kwargs)),
			timeout=timeout)
	except asyncio.TimeoutError:
		pass
	if not times: return float('infinity')
	return sum(times) / trace(len(times), end=' ', flush=True)

stdsizes = (1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000,
	20000, 50000, 100000, 200000, 500000, 1000000, 2000000, 5000000, 10000000)

#  stdsizes = stdsizes[:13]

async def make_plot(filename, stmts:dict[str,dict[int,'task']], *args, **kwargs):
	trace('-' * 20, filename, '-' * 20)
	plt.xscale('log')
	plt.yscale('log')
	for name, times in stmts.items():
		trace('-' * 10, name, '-' * 10)
		xs, ys = zip(*[(trace(k, end=' ', flush=True), trace(await v))
			for k, v in times.items()])
		plt.plot(xs, ys, label=name)
	plt.legend()
	plt.savefig(filename)
	plt.clf()

def del_index(xs, n):
	del xs[n]

plots = [
	make_plot('plots/construction.png', {
		'list(range(n))': {size:
			timeit(lambda n: list(range(n)), largs=(size,))
			for size in stdsizes},
		'deque(range(n))': {size:
			timeit(lambda n: deque(range(n)), largs=(size,))
			for size in stdsizes},
		'pvector(range(n))': {size:
			timeit(lambda n: pvector(range(n)), largs=(size,))
			for size in stdsizes},
		'pdeque(range(n))': {size:
			timeit(lambda n: pdeque(range(n)), largs=(size,))
			for size in stdsizes},
		'psequence(range(n))': {size:
			timeit(lambda n: psequence(range(n)), largs=(size,))
			for size in stdsizes},
	}),
	make_plot('plots/get_left.png', {
		'list[0]': {size:
			timeit(lambda xs: xs[0], largs=(size,),
				setup=lambda n: (generate(list, n),))
			for size in stdsizes},
		'deque[0]': {size:
			timeit(lambda xs: xs[0], largs=(size,),
				setup=lambda n: (generate(deque, n),))
			for size in stdsizes},
		'pvector[0]': {size:
			timeit(lambda xs: xs[0], largs=(size,),
				setup=lambda n: (generate(pvector, n),))
			for size in stdsizes},
		'pdeque.left': {size:
			timeit(lambda xs: xs.left, largs=(size,),
				setup=lambda n: (generate(pdeque, n),))
			for size in stdsizes},
		'psequence.left': {size:
			timeit(lambda xs: xs.left, largs=(size,),
				setup=lambda n: (generate(psequence, n),))
			for size in stdsizes},
	}),
	make_plot('plots/get_right.png', {
		'list[-1]': {size:
			timeit(lambda xs: xs[-1], largs=(size,),
				setup=lambda n: (generate(list, n),))
			for size in stdsizes},
		'deque[-1]': {size:
			timeit(lambda xs: xs[-1], largs=(size,),
				setup=lambda n: (generate(deque, n),))
			for size in stdsizes},
		'pvector[-1]': {size:
			timeit(lambda xs: xs[-1], largs=(size,),
				setup=lambda n: (generate(pvector, n),))
			for size in stdsizes},
		'pdeque.right': {size:
			timeit(lambda xs: xs.right, largs=(size,),
				setup=lambda n: (generate(pdeque, n),))
			for size in stdsizes},
		'psequence.right': {size:
			timeit(lambda xs: xs.right, largs=(size,),
				setup=lambda n: (generate(psequence, n),))
			for size in stdsizes},
	}),
	make_plot('plots/get_middle.png', {
		'list[len/2]': {size:
			timeit(lambda xs, n: xs[n], largs=(size,),
				setup=lambda n: (generate(list, n), n // 2))
			for size in stdsizes},
		'deque[len/2]': {size:
			timeit(lambda xs, n: xs[n], largs=(size,),
				setup=lambda n: (generate(deque, n), n // 2))
			for size in stdsizes},
		'pvector[len/2]': {size:
			timeit(lambda xs, n: xs[n], largs=(size,),
				setup=lambda n: (generate(pvector, n), n // 2))
			for size in stdsizes},
		'pdeque[len/2]': {size:
			timeit(lambda xs, n: xs[n], largs=(size,),
				setup=lambda n: (generate(pdeque, n), n // 2))
			for size in stdsizes},
		'psequence[len/2]': {size:
			timeit(lambda xs, n: xs[n], largs=(size,),
				setup=lambda n: (generate(psequence, n), n // 2))
			for size in stdsizes},
	}),
	make_plot('plots/insert_left.png', {
		'list.insert(0, 0)': {size:
			timeit(lambda xs: xs.insert(0, 0), largs=(size,),
				setup=lambda n: (generate(list, n),))
			for size in stdsizes},
		'deque.appendleft(0)': {size:
			timeit(lambda xs: xs.appendleft(0), largs=(size,),
				setup=lambda n: (generate(deque, n),))
			for size in stdsizes},
		'pvector([0]) + pvector(xs)': {size:
			timeit(lambda xs: pvector([0]) + xs, largs=(size,),
				setup=lambda n: (generate(pvector, n),))
			for size in stdsizes},
		'pdeque.appendleft(0)': {size:
			timeit(lambda xs: xs.appendleft(0), largs=(size,),
				setup=lambda n: (generate(pdeque, n),))
			for size in stdsizes},
		'psequence.appendleft(0)': {size:
			timeit(lambda xs: xs.appendleft(0), largs=(size,),
				setup=lambda n: (generate(psequence, n),))
			for size in stdsizes},
	}),
	make_plot('plots/insert_right.png', {
		'list.append(0)': {size:
			timeit(lambda xs: xs.append(0), largs=(size,),
				setup=lambda n: (generate(list, n),))
			for size in stdsizes},
		'deque.append(0)': {size:
			timeit(lambda xs: xs.append(0), largs=(size,),
				setup=lambda n: (generate(deque, n),))
			for size in stdsizes},
		'pvector.append(0)': {size:
			timeit(lambda xs: xs.append(0), largs=(size,),
				setup=lambda n: (generate(pvector, n),))
			for size in stdsizes},
		'pdeque.append(0)': {size:
			timeit(lambda xs: xs.append(0), largs=(size,),
				setup=lambda n: (generate(pdeque, n),))
			for size in stdsizes},
		'psequence.append(0)': {size:
			timeit(lambda xs: xs.append(0), largs=(size,),
				setup=lambda n: (generate(psequence, n),))
			for size in stdsizes},
	}),
	make_plot('plots/insert_middle.png', {
		'list.insert(len/2, 0)': {size:
			timeit(lambda xs, n: xs.insert(n, 0), largs=(size,),
				setup=lambda n: (generate(list, n), n // 2))
			for size in stdsizes},
		'deque.insert(len/2, 0)': {size:
			timeit(lambda xs, n: xs.insert(n, 0), largs=(size,),
				setup=lambda n: (generate(deque, n), n // 2))
			for size in stdsizes},
		'pvector[:len/2] + [0] + pvector[len/2:]': {size:
			timeit(lambda xs, n: xs[:n] + [0] + xs[n:], largs=(size,),
				setup=lambda n: (generate(pvector, n), n // 2))
			for size in stdsizes},
		'pdeque[:len/2].append(0).extend(pdeque[len/2:])': {size:
			timeit(lambda xs, n: xs[:n].append(0).extend(xs[n:]), largs=(size,),
				setup=lambda n: (generate(pdeque, n), n // 2))
			for size in stdsizes},
		'psequence.insert(len/2, 0)': {size:
			timeit(lambda xs, n: xs.insert(n, 0), largs=(size,),
				setup=lambda n: (generate(psequence, n), n // 2))
			for size in stdsizes},
	}),
	make_plot('plots/delete_left.png', {
		'list.pop(0)': {size:
			timeit(lambda xs: xs.pop(0), largs=(size,),
				setup=lambda n: (generate(list, n),))
			for size in stdsizes},
		'deque.popleft()': {size:
			timeit(lambda xs: xs.popleft(), largs=(size,),
				setup=lambda n: (generate(deque, n),))
			for size in stdsizes},
		'pvector.delete(0)': {size:
			timeit(lambda xs: xs.delete(0), largs=(size,),
				setup=lambda n: (generate(pvector, n),))
			for size in stdsizes},
		'pdeque.popleft()': {size:
			timeit(lambda xs: xs.popleft(), largs=(size,),
				setup=lambda n: (generate(pdeque, n),))
			for size in stdsizes},
		'psequence.viewleft()': {size:
			timeit(lambda xs: xs.viewleft(), largs=(size,),
				setup=lambda n: (generate(psequence, n),))
			for size in stdsizes},
	}),
	make_plot('plots/delete_right.png', {
		'list.pop()': {size:
			timeit(lambda xs: xs.pop(), largs=(size,),
				setup=lambda n: (generate(list, n),))
			for size in stdsizes},
		'deque.pop()': {size:
			timeit(lambda xs: xs.pop(), largs=(size,),
				setup=lambda n: (generate(deque, n),))
			for size in stdsizes},
		'pvector.delete(-1)': {size:
			timeit(lambda xs: xs.delete(-1), largs=(size,),
				setup=lambda n: (generate(pvector, n),))
			for size in stdsizes},
		'pdeque.pop()': {size:
			timeit(lambda xs: xs.pop(), largs=(size,),
				setup=lambda n: (generate(pdeque, n),))
			for size in stdsizes},
		'psequence.viewright()': {size:
			timeit(lambda xs: xs.viewright(), largs=(size,),
				setup=lambda n: (generate(psequence, n),))
			for size in stdsizes},
	}),
	make_plot('plots/delete_middle.png', {
		'list.pop(len / 2)': {size:
			timeit(lambda xs, n: xs.pop(n), largs=(size,),
				setup=lambda n: (generate(list, n), n // 2))
			for size in stdsizes},
		'del deque[len / 2]': {size:
			timeit(del_index, largs=(size,),
				setup=lambda n: (generate(deque, n), n // 2))
			for size in stdsizes},
		'pvector.delete(len/2)': {size:
			timeit(lambda xs, n: xs.delete(n), largs=(size,),
				setup=lambda n: (generate(pvector, n), n // 2))
			for size in stdsizes},
		'pdeque[:len/2].extend(pdeque[len/2+1:])': {size:
			timeit(lambda xs, n: xs[:n].extend(xs[n+1:]), largs=(size,),
				setup=lambda n: (generate(pdeque, n), n // 2))
			for size in stdsizes},
		'psequence.delete(len/2)': {size:
			timeit(lambda xs, n: xs.delete(n), largs=(size,),
				setup=lambda n: (generate(psequence, n), n // 2))
			for size in stdsizes},
	}),
	make_plot('plots/extend.png', {
		'list.extend(list)': {size:
			timeit(lambda xs: xs.extend(xs), largs=(size,),
				setup=lambda n: (generate(list, n),))
			for size in stdsizes},
		'deque.extend(deque)': {size:
			timeit(lambda xs: xs.extend(xs), largs=(size,),
				setup=lambda n: (generate(deque, n),))
			for size in stdsizes},
		'pvector.extend(pvector)': {size:
			timeit(lambda xs: xs.extend(xs), largs=(size,),
				setup=lambda n: (generate(pvector, n),))
			for size in stdsizes},
		'pdeque.extend(pdeque)': {size:
			timeit(lambda xs: xs.extend(xs), largs=(size,),
				setup=lambda n: (generate(pdeque, n),))
			for size in stdsizes},
		'psequence.extend(psequence)': {size:
			timeit(lambda xs: xs.extend(xs), largs=(size,),
				setup=lambda n: (generate(psequence, n),))
			for size in stdsizes},
	}),
	make_plot('plots/repeat.png', {
		'list * len': {size:
			timeit(lambda xs, n: xs * n, largs=(size,),
				setup=lambda n: (generate(list, n), n))
			for size in stdsizes if size * size <= stdsizes[-1]},
		'deque * len': {size:
			timeit(lambda xs, n: xs * n, largs=(size,),
				setup=lambda n: (generate(deque, n), n))
			for size in stdsizes if size * size <= stdsizes[-1]},
		'pvector * len': {size:
			timeit(lambda xs, n: xs * n, largs=(size,),
				setup=lambda n: (generate(pvector, n), n))
			for size in stdsizes if size * size <= stdsizes[-1]},
		'pdeque * len': {size:
			timeit(lambda xs, n: xs * n, largs=(size,),
				setup=lambda n: (generate(pdeque, n), n))
			for size in stdsizes if size * size <= stdsizes[-1]},
		'psequence * len': {size:
			timeit(lambda xs, n: xs * n, largs=(size,),
				setup=lambda n: (generate(psequence, n), n))
			for size in stdsizes if size * size <= stdsizes[-1]},
	}),
	make_plot('plots/slice_chunk.png', {
		'list[len/2:]': {size:
			timeit(lambda xs, n: xs[n:], largs=(size,),
				setup=lambda n: (generate(list, n), n // 2))
			for size in stdsizes},
		'deque[len/2:]': {size:
			timeit(lambda xs, n: xs[n:], largs=(size,),
				setup=lambda n: (generate(deque, n), n // 2))
			for size in stdsizes},
		'pvector[len/2:]': {size:
			timeit(lambda xs, n: xs[n:], largs=(size,),
				setup=lambda n: (generate(pvector, n), n // 2))
			for size in stdsizes},
		'pdeque[len/2:]': {size:
			timeit(lambda xs, n: xs[n:], largs=(size,),
				setup=lambda n: (generate(pdeque, n), n // 2))
			for size in stdsizes},
		'psequence[len/2:]': {size:
			timeit(lambda xs, n: xs[n:], largs=(size,),
				setup=lambda n: (generate(psequence, n), n // 2))
			for size in stdsizes},
	}),
	make_plot('plots/slice_step.png', {
		'list[::len/100]': {size:
			timeit(lambda xs, n: xs[::n], largs=(size,),
				setup=lambda n: (generate(list, n), max(1, n // 100)))
			for size in stdsizes if size > 100},
		'deque[::len/100]': {size:
			timeit(lambda xs, n: xs[::n], largs=(size,),
				setup=lambda n: (generate(deque, n), max(1, n // 100)))
			for size in stdsizes if size > 100},
		'pvector[::len/100]': {size:
			timeit(lambda xs, n: xs[::n], largs=(size,),
				setup=lambda n: (generate(pvector, n), max(1, n // 100)))
			for size in stdsizes if size > 100},
		'pdeque[::len/100]': {size:
			timeit(lambda xs, n: xs[::n], largs=(size,),
				setup=lambda n: (generate(pdeque, n), max(1, n // 100)))
			for size in stdsizes if size > 100},
		'psequence[::len/100]': {size:
			timeit(lambda xs, n: xs[::n], largs=(size,),
				setup=lambda n: (generate(psequence, n), max(1, n // 100)))
			for size in stdsizes if size > 100},
	}),
]

async def main():
	trace('-' * 20, 'generate', '-' * 20)
	for what in [list, deque, pvector, pdeque, psequence]:
		trace('-' * 10, what, '-' * 10)
		for size in stdsizes:
			generate(what, trace(size))
	for plot in plots:
		await plot

asyncio.run(main())