Newbie: How to run simple code with numba

[Raphael C]

I am attempting to run this relatively simple code

from random import *
from time import time
from itertools import*
from numba import autojit

@autojit
def perm_ryser(a): # Ryser's formula, using matrix entries
    maxn = len(a)
    n_list = range(1,maxn+1)
    s_list = chain.from_iterable(combinations(n_list,i) for i in range(maxn+1))
    total = 0
    for st in s_list:
        stotal = (-1)**len(st)
        for i in xrange(maxn):
            stotal *= sum(a[i][j-1] for j in st)
        total += stotal
    return total*((-1)**maxn)
   

def genmatrix(d):
    mat = []
    for x in xrange(d):
        row = []
        for y in xrange(d):
            row.append([-1,1][randrange(0,2)])
        mat.append(row)
    return mat

def main():
    for i in xrange(1,25):
        k = genmatrix(i)
        print 'Matrix: (%dx%d)'%(i,i)
        print '\n'.join('['+', '.join(`j`.rjust(2) for j in a)+']' for a in k)
        print 'Permanent:',
        t = time()
        p = perm_ryser(k)
        print p,'(took',time()-t,'seconds)'

if __name__ == '__main__':
    main()



I get

[..]
    p = perm_ryser(k)
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/dispatcher.py", line 286, in _compile_for_args
    return self.compile(tuple(argtypes))
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/dispatcher.py", line 532, in compile
    cres = self._compiler.compile(args, return_type)
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/dispatcher.py", line 81, in compile
    flags=flags, locals=self.locals)
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/compiler.py", line 684, in compile_extra
    return pipeline.compile_extra(func)
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/compiler.py", line 348, in compile_extra
    return self._compile_bytecode()
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/compiler.py", line 649, in _compile_bytecode
    return self._compile_core()
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/compiler.py", line 636, in _compile_core
    res = pm.run(self.status)
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/compiler.py", line 235, in run
    raise patched_exception
AttributeError: Caused By:
Traceback (most recent call last):
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/compiler.py", line 227, in run
    stage()
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/compiler.py", line 362, in stage_analyze_bytecode
    func_ir = translate_stage(self.func_id, self.bc)
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/compiler.py", line 747, in translate_stage
    return interp.interpret(bytecode)
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/interpreter.py", line 97, in interpret
    self.dfa.run()
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/dataflow.py", line 27, in run
    self.infos[blk.offset] = self.run_on_block(blk)
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/dataflow.py", line 71, in run_on_block
    self.dispatch(info, inst)
  File "/home/user/miniconda2/lib/python2.7/site-packages/numba/dataflow.py", line 80, in dispatch
    fn = getattr(self, fname)
AttributeError: 'DataFlowAnalysis' object has no attribute 'op_STORE_DEREF'

Failed at object (analyzing bytecode)
'DataFlowAnalysis' object has no attribute 'op_STORE_DEREF'



What should I be doing instead?

Raphael

[Siu Kwan Lam]

The error is likely due to this line

    s_list = chain.from_iterable(combinations(n_list,i) for i in range(maxn+1))

There are two unsupported features here:

1) nested function due to the comprehension

2) itertools

BTW, `autojit` is `jit` now.  

--
You received this message because you are subscribed to the Google Groups "Numba Public Discussion - Public" group.
To unsubscribe from this group and stop receiving emails from it, send an email to numba-users...@continuum.io.
To post to this group, send email to numba...@continuum.io.
To view this discussion on the web visit https://groups.google.com/a/continuum.io/d/msgid/numba-users/e714162e-9a23-4fc8-87f7-516fdb3ed313%40continuum.io.
For more options, visit https://groups.google.com/a/continuum.io/d/optout.

--

Siu Kwan Lam

Software Engineer

Continuum Analytics

[Raphael C]

Thank you. Looks like I need to remove itertools as a first step.

Raphael

> https://groups.google.com/a/continuum.io/d/msgid/numba-users/CAHjo7%3DV1kNKxkW64J8kp7A5xQb%2Bz2P-uv8o20_39oVKKXCZLgw%40mail.gmail.com.

[Raphael C]

My second attempt to use numba also fails but this time with a
different error message. My code is

import numpy as np
import itertools
from math import factorial as fac
import sys
from numba import jit


@jit
def fast_glynn_perm(M):
row_comb = []
for column in range(len(M[0])):
t = 0
for row in M:
t += row[column]
row_comb.append(t)
n=len(M)

total = 0
old_grey = 0
sign = +1

num_loops = 2**(n-1)

for bin_index in xrange(1, num_loops + 1):
i_product = 1
for row_num in row_comb:
i_product = i_product * row_num
total += sign * i_product
new_grey = bin_index^(bin_index/2)
grey_diff = old_grey ^ new_grey
grey_diff_index = grey_diff.bit_length()-1
new_vector = M[grey_diff_index]
direction = 2 * cmp(old_grey,new_grey)

for i in range(n):
row_comb[i] += new_vector[i] * direction

sign = -sign
old_grey = new_grey

return total/num_loops


def rvs(dim=3):
random_state = np.random
H = np.eye(dim)
D = np.ones((dim,))
for n in range(1, dim):
x = random_state.normal(size=(dim-n+1,))
D[n-1] = np.sign(x[0])
x[0] -= D[n-1]*np.sqrt((x*x).sum())
# Householder transformation
Hx = (np.eye(dim-n+1) - 2.*np.outer(x, x)/(x*x).sum())
mat = np.eye(dim)
mat[n-1:, n-1:] = Hx
H = np.dot(H, mat)
# Fix the last sign such that the determinant is 1
D[-1] = (-1)**(1-(dim % 2))*D.prod()
# Equivalent to np.dot(np.diag(D), H) but faster, apparently
H = (D*H.T).T
return H

p = 6

U = rvs(p**2)

A = U[:,:p]

probs = []
A = A.tolist()

num= num_withreplacement(p*p,p)

flag = 0
for subset in itertools.combinations_with_replacement(range(p**2),p):
AS = [A[i] for i in subset]
factors = [fac(subset.count(i)) for i in set(subset)]
norm_factor = 1.0
for factor in factors:
norm_factor = norm_factor * factor
prob = fast_glynn_perm(AS)**2
probs.append(fast_glynn_perm(AS)**2/norm_factor)


This code runs in python without error if I remove the @jit line.
However using numba I get

Traceback (most recent call last):

File "boson.py", line 129, in <module>
prob = fast_glynn_perm(AS)**2
ValueError: cannot compute fingerprint of empty list

Raphael

[kas...@gmail.com]

Hey,

There are some things missing from your code, so i cant run it. For example "num_withreplacement"   and "cmp". For me it also fails at the XOR operator because bin_index/2 results in a float, but that might be due to different version of Python.

Also, if you want to make it faster, try creating structures in advance instead of appending to a list if you know the size beforehand. You could for example create an array for "row_comb" of size "len(M[0])". But i cant test those things because the code doesnt run.



Regards,
Rutger

[Raphael C]

Apologies the code wasn't right. Here is a simpler and better version.
I am using python 2.7.12.


---

#!/usr/bin/env python
from operator import mul

import numpy as np
import itertools

import sys
from numba import jit

@jit
def fast_glynn_perm(M):
row_comb = []
for column in range(len(M[0])):
t = 0
for row in M:
t += row[column]
row_comb.append(t)
n=len(M)

total = 0
old_grey = 0
sign = +1

# binary_power_dict = {2**i:i for i in range(n)}

num_loops = 2**(n-1)

for bin_index in xrange(1, num_loops + 1):
i_product = 1
for row_num in row_comb:
i_product = i_product * row_num
total += sign * i_product

# total += sign * reduce(mul, row_comb)

new_grey = bin_index^(bin_index/2)
grey_diff = old_grey ^ new_grey
grey_diff_index = grey_diff.bit_length()-1

# grey_diff_index = binary_power_dict[grey_diff]

new_vector = M[grey_diff_index]
direction = 2 * cmp(old_grey,new_grey)

for i in range(n):
row_comb[i] += new_vector[i] * direction

sign = -sign
old_grey = new_grey

return total/num_loops

p = 6

A = np.random.rand(p,p)
AS = A.tolist()

print fast_glynn_perm(AS)

---

If you remove the "@jit" and the "import numba import jit" lines it
runs fine. If you include them you get

File "boson-test.py", line 56, in <module>
print fast_glynn_perm(AS)

ValueError: cannot compute fingerprint of empty list

> https://groups.google.com/a/continuum.io/d/msgid/numba-users/f988ebaf-1528-4137-bcd6-c9237ec4b0af%40continuum.io.

[kas...@gmail.com]

Hey,

Thanks for the update, this replicates the error indeed. It has to do with the row_comb list you initialize. If you replace it with an array, you should be able to use Numba. If you use njit instead of jit, you enforce nopython mode, and this way you can be sure that your getting a good (potential) speedup, because Numba isnt allowed to fallback on Python object-mode when running the code.

I work in Python 3.4, so i had to change a few things to get it running, xrange becomes range, cmp() doesnt exist anymore (becomes (a > b) - (a < b)), and // is needed for integer division. The .bit_length also isnt available in Numba.

The code then becomes:

@njit
def bitcounter(n):
    # from http://stackoverflow.com/a/2654159/1755432
    if n == 0:
        return 0
    else:
        return int(np.floor(np.log2(n)) + 1)
   
@njit
def fast_glynn_perm_numba(M):
   
    ys, xs = M.shape
   
    row_comb = np.zeros((ys), dtype=M.dtype)
   
    for column in range(xs):
        for row in range(ys):
            row_comb[column] += M[row, column]

       
    n=len(M)

    total = 0
    old_grey = 0
    sign = +1

    num_loops = 2**(n-1)

    for bin_index in range(1, num_loops + 1):

        i_product = 1
        for row_num in row_comb:
            i_product = i_product * row_num
        total += sign *

i_product

        new_grey = bin_index^(bin_index//2)
        grey_diff = old_grey^new_grey
       
        grey_diff_index = bitcounter(grey_diff)-1

        new_vector = M[grey_diff_index]
   
        direction = 2 * (old_grey > new_grey) - (old_grey < new_grey)

        for i in range(n):
            row_comb[i] += new_vector[i] * direction

        sign = -sign
        old_grey = new_grey

    return total/num_loops

Running this i get a speedup of about 75x over your Python version. Here is the notebook i used:
http://nbviewer.jupyter.org/gist/RutgerK/bbf2137dd85c9abc8b555195f10886d3

I have absolutely no clue what the code does, so check the results carefully if you use my changed version. A quick check reveals identical results compared to the Python version.


Regards,
Rutger