After some experiments, it looks like bind() is already pretty fast. The only way to increase its performance is to rewrite it in C.

I tried to approaches:

1. Refactor ._bind() to produce a high-level instruction set that can be cached, and is fast to iterate through and build BoundArguments.  Repo: https://github.com/1st1/cpython/tree/bind

Results:

====================================  ===========  ==============  ===============
function / call                       bind (3.4)   bind cache hit  bind cache miss
====================================  ===========  ==============  ===============
() / ()                               0.716s       0.746s  (-4%)   0.799s  (-10%)
(a, b=1) / (10)                       1.140s       0.910s  (+20%)  1.294s  (-12%)
(a, b=1, *ar) / (10, 20, 30, 40)      1.352s       1.145s  (+15%)  1.520s  (-11%)
(a, b=1, **ar) / (10, 20, z=30, y=4)  1.364s       1.233s  (+10%)  1.660s  (-18%)
(a, b=1, *, z, **ar) / (1,2,z=3,y=4)  1.499s       1.363s  (+10%)  1.897s  (-26%)


2. Refactor ._bind() to compile a function that builds BoundArguments for te given args/kwargs shape.  This approach yields more-or-less same results as (1), but performance of cache-miss case is just terrible (-200%).  Compiling functions on the fly is expensive.  Repo to play with: https://github.com/1st1/cpython/tree/bind_jit


I'm closing this issue, until I (or someone else) can implement bind() in C (or come up with a faster pure-python implementation).