Can you make this faster?

[Kamilche]

I have a routine that I really need, but it slows down processing
significantly. Can you spot any ineffeciencies in the code?

This code makes a critical function of mine run about 7x slower than
using a prebuilt format string. For maximum flexibility, it would be
best to calculate the format string using this method, so I'd dearly
love to keep it.

def fmtstring(args) :
delim = '\0'
fmt = []
fmt.append('<')
for arg in args:
t = type(arg)
if t == types.StringTyp e:
l = len(arg)
fmt.append(str( l) + 's')
elif t == types.IntType:
fmt.append('i')
elif t == types.LongType:
fmt.append('q')
elif t == types.BooleanTy pe:
fmt.append('c')
elif t == types.FloatType :
fmt.append('d')
else:
raise Exception("Can' t pack argument of type %s!" % t)
s = ''.join(fmt)
s = s + '\0'
return s

[Roy Smith]

Re: Can you make this faster?

In article <889cbba0.04062 71022.fd1f9ac@p osting.google.c om>,
klachemin@home. com (Kamilche) wrote:
[color=blue]
> I have a routine that I really need, but it slows down processing
> significantly. Can you spot any ineffeciencies in the code?
>
> This code makes a critical function of mine run about 7x slower than
> using a prebuilt format string. For maximum flexibility, it would be
> best to calculate the format string using this method, so I'd dearly
> love to keep it.
>
> def fmtstring(args) :
> delim = '\0'
> fmt = []
> fmt.append('<')
> for arg in args:
> t = type(arg)
> if t == types.StringTyp e:
> l = len(arg)
> fmt.append(str( l) + 's')
> elif t == types.IntType:
> fmt.append('i')
> elif t == types.LongType:
> fmt.append('q')
> elif t == types.BooleanTy pe:
> fmt.append('c')
> elif t == types.FloatType :
> fmt.append('d')
> else:
> raise Exception("Can' t pack argument of type %s!" % t)
> s = ''.join(fmt)
> s = s + '\0'
> return s[/color]

The first thing is to profile your code and make sure this really is
significant in the overall scheme of things. From your description, it
sounds like you've already done that, so I'll go with that assumption.

What's the most likely value for type(arg)? If 90% of your args are
floats, for example, most of the time you work your way all the way down
the if/else tree before getting to the right spot. Putting the tests in
order of probability of occurance will help you a little.

Doing "from types import *" and then being able to just say "IntType"
instead of "types.IntT ype" will be a little faster since there will be
one less name lookup.

Another thing you can try is doing dictionary lookups instead of an
if/else tree. Something like:

map = {IntType: 'i',
LongType: 'q',
BooleanType: 'c',
FloatType: 'd'}
[...]
try:
fmt.append (map[t])
except KeyError:
raise Exception ("Can't pack %s" % t)

You still need to special-case StringType, however.

Lastly, is an idea which is really quite gross. If you're desperate for
speed, the majority of your args are strings, and you have no pride, it
might be worth trying, however. Instead of saying:

t = type(arg)
if t == types.StringTyp e:
l = len(arg)

you could do something like:

try:
l = len (arg)
fmt.append(str( l) + 's')
except TypeError:
process all the non-string types

The idea here is to not waste time getting and testing the type, just
assume it's a string and deal with the consequences later if your
assumption was wrong. In real life, this plays out as, "It's easier to
ask forgiveness than permission".

Of the types you mentioned, string is the only one which which has a
length; all the others will raise TypeError when passed to len().
Exception processing is relatively slow, but if it only happens a small
percentage of the time, you might be ahead of the game this way.

Some people would call this elegant, others would call it a gross hack.
I guess it depends on your perspective, and how desperate you are to
make your code run faster :-)

Of course, you could put several of these ideas together. Try the
exception-catching idea for strings first, and then sort out the other 4
types using a dictionary lookup.

My gut feeling is that even with all these tricks, the best you'll be
seeing is a factor of 2 or 3 speedup. I'd be amazed if you could get
anywhere near the 7x you're looking for.

[Martin v. Löwis]

Re: Can you make this faster?

Kamilche wrote:[color=blue]
> I have a routine that I really need, but it slows down processing
> significantly. Can you spot any ineffeciencies in the code?[/color]

I would use a dictionary, and I would pre-allocate the result list:

_code = {types.StringTy pe: 's',
types.IntType: 'i',
types.LongType: 'q',
types.BooleanTy pe: 'c',
types.FloatType : 'd'
}
def fmtstring(args) :
fmt = ['\0']*(len(args)+1)
fmt.append('<')
for i, arg in enumerate(args) :
t = type(arg)
try:
c = _code[t]
except KeyError:
raise Exception("Can' t pack argument of type %s!" % t)
if c == 's':
fmt[i] = str(len(arg))+' s'
else:
fmt[i] = c
return ''.join(fmt)

Regards,
Martin

[Martin v. Löwis]

Re: Can you make this faster?

Kamilche wrote:[color=blue]
> I have a routine that I really need, but it slows down processing
> significantly. Can you spot any ineffeciencies in the code?[/color]

I would use a dictionary, and I would pre-allocate the result list:

_code = {types.StringTy pe: 's',
types.IntType: 'i',
types.LongType: 'q',
types.BooleanTy pe: 'c',
types.FloatType : 'd'
}
def fmtstring(args) :
fmt = ['\0']*(len(args)+1)
fmt.append('<')
for i, arg in enumerate(args) :
t = type(arg)
try:
c = _code[t]
except KeyError:
raise Exception("Can' t pack argument of type %s!" % t)
if c == 's':
fmt[i] = str(len(arg))+' s'
else:
fmt[i] = c
return ''.join(fmt)

Regards,
Martin

[alejandro david weil]

Re: Can you make this faster?

On Sun June 27 2004 15:22, Kamilche wrote:[color=blue]
> I have a routine that I really need, but it slows down processing
> significantly. Can you spot any ineffeciencies in the code?
>
> This code makes a critical function of mine run about 7x slower than
> using a prebuilt format string. For maximum flexibility, it would be
> best to calculate the format string using this method, so I'd dearly
> love to keep it.
>
> def fmtstring(args) :
> delim = '\0'
> fmt = []
> fmt.append('<')
> for arg in args:
> t = type(arg)
> if t == types.StringTyp e:
> l = len(arg)
> fmt.append(str( l) + 's')
> elif t == types.IntType:
> fmt.append('i')
> elif t == types.LongType:
> fmt.append('q')
> elif t == types.BooleanTy pe:
> fmt.append('c')
> elif t == types.FloatType :
> fmt.append('d')
> else:
> raise Exception("Can' t pack argument of type %s!" % t)
> s = ''.join(fmt)
> s = s + '\0'
> return s[/color]

I've tried this:
import types

def fmtstring(args) :
delim = '\0'
fmt = []
fmt.append('<')
for arg in args:
t = type(arg)
if t == types.StringTyp e:
l = len(arg)
fmt.append(str( l) + 's')
elif t == types.IntType:
fmt.append('i')
elif t == types.LongType:
fmt.append('q')
elif t == types.BooleanTy pe:
fmt.append('c')
elif t == types.FloatType :
fmt.append('d')
else:
raise Exception("Can' t pack argument of type %s!" % t)
s = ''.join(fmt)
s = s + '\0'
return s

typedic = {
types.StringTyp e : 's',
types.IntType: 'i',
types.LongType: 'q',
types.BooleanTy pe: 'c',
types.FloatType :'d'}

def myfmtstring(arg s):
global typedic
f2 = '<'
t = None
for arg in args:
t = type(arg)
if t == types.StringTyp e:
f2 += str(len(arg))
try:
f2 += typedic[t]
except: #check the exception here!
raise Exception("Can' t pack argument of type %s!" % t)
return f2+'\0'

if __name__=='__ma in__':
import unittest
TIMES = 10000

class TestFmtFuncBase (unittest.TestC ase):
def setUp(self):
self.what = ['hola','que','t al',324,454,Fal se]

def runFuncOnce(sel f):
#shouldnt be here!
assert(False)

def runFuncTimes(se lf, times=TIMES):
for i in xrange(times):
self.runFuncOnc e()


class TestFunction1(T estFmtFuncBase) :
def runFuncOnce(sel f):
return fmtstring(self. what)
def testSpeed(self) :
"""Run function a lot of times to check its time"""
self.runFuncTim es()
def testValue(self) :
"""Check return value"""
print self.runFuncOnc e()

class TestFunction2(T estFmtFuncBase) :
def runFuncOnce(sel f):
return myfmtstring(sel f.what)
def testSpeed(self) :
"""Run function a lot of times to check its time"""
self.runFuncTim es()
def testValue(self) :
"""Check return value"""
print self.runFuncOnc e()


suiteOriginal = unittest.TestSu ite()
suiteOriginal.a ddTest(unittest .makeSuite(Test Function1))
suiteNew = unittest.TestSu ite()
suiteNew.addTes t(unittest.make Suite(TestFunct ion2))

unittest.TextTe stRunner(verbos ity=2).run(suit eOriginal)
unittest.TextTe stRunner(verbos ity=2).run(suit eNew)

And seems to be not faster:

----------------------------------------------------------------------
Run function a lot of times to check its time ... ok
Check return value ... <4s3s3siic
ok

----------------------------------------------------------------------
Ran 2 tests in 0.477s

OK
Run function a lot of times to check its time ... ok
Check return value ... <4s3s3siic
ok

----------------------------------------------------------------------
Ran 2 tests in 0.396s

OK


But, anyway, the problem seems to be the:
f2 += str(len(arg))
line.

If you take it off, you'll see that time reduces to half!
Why? How to fix?
Don't know! :-(

Sorry,
dave
--
+ There is no dark side of the moon really. Matter of fact it's all dark.

[alejandro david weil]

Re: Can you make this faster?

On Sun June 27 2004 18:51, alejandro david weil wrote:[color=blue][color=green]
> > But, anyway, the problem seems to be the:
> > f2 += str(len(arg))
> > line.
> >
> > If you take it off, you'll see that time reduces to half!
> > Why? How to fix?
> > Don't know! :-([/color]
>
> For example, this seems to be "better":[/color]

Well, that was not optimized and some debug print remains, this,
uses half time:

typedic = {
types.IntType: 'i',
types.LongType: 'q',
types.BooleanTy pe: 'c',
types.FloatType :'d'}

slen = {}
for i in xrange(256):
slen[i]=str(i)+'s'

def myfmtstring(arg s):
global typedic, slen
f2 = '<'
t = None
for arg in args:
t = type(arg)
if t == types.StringTyp e:
try:
f2+=slen[len(arg)]
except:
f2 += str(len(arg))+' s'
else:
try:
f2 += typedic[t]
except: #check the exception here!
raise Exception("Can' t pack argument of type %s!" % t)
return f2+'\0'

-> Ran 2 tests in 0.253s



Also I tried the except-catch method proposed, in this way, and got ugly results:
(removing StringType from typedic)

def my_slowest_fmts tring(args):
global typedic, slen
f2 = '<'
t = None
for arg in args:
t = type(arg)
try:
f2 += typedic[t]
except: #check the exception here!
if t == types.StringTyp e:
try:
f2+=slen[len(arg)]
except:
f2 += str(len(arg))+' s'
else:
raise Exception("Can' t pack argument of type %s!" % t)
return f2+'\0'

-> Ran 2 tests in 0.632s (worst than the first version! that gives: Ran 2 tests in 0.465s)
--
+ There is no dark side of the moon really. Matter of fact it's all dark.

[alejandro david weil]

Re: Can you make this faster?

>[color=blue]
> But, anyway, the problem seems to be the:
> f2 += str(len(arg))
> line.
>
> If you take it off, you'll see that time reduces to half!
> Why? How to fix?
> Don't know! :-([/color]

For example, this seems to be "better":

typedic = {
types.StringTyp e : 's',
types.IntType: 'i',
types.LongType: 'q',
types.BooleanTy pe: 'c',
types.FloatType :'d'}



slen = {}
for i in xrange(256):
slen[i]=str(i)


def myfmtstring(arg s):
global typedic, slen
f2 = '<'
t = None
for arg in args:
t = type(arg)
if t == types.StringTyp e:
try:
f2+=slen[len(arg)]
except:
print 'aca'
f2 += str(len(arg))
try:
f2 += typedic[t]
except: #check the exception here!
raise Exception("Can' t pack argument of type %s!" % t)
return f2+'\0'




--
+ There is no dark side of the moon really. Matter of fact it's all dark.