Speedup Bitmap Parser

[Jayson Santos]

Hello people, I'm writing a Bitmap parser for study purposes, however
when I parse a bitmap file and when I paint that file in a window, the
script take to much time.
How can I optimize my script loops to be faster ?

Here is the script

http://pastebin.com/m652b8d65

Best Regards
Jayson Reis

 

[Terry Reedy]

Hello people, I'm writing a Bitmap parser for study purposes, however
when I parse a bitmap file and when I paint that file in a window, the
script take to much time.

1. You turned constants into static methods called for every line,
adding attribute lookup and function call time.
2. You read the image a line at a time and break each line into separate
pixel objects.
3. You paint each pixel by drawing and filling a 1-pixel rectangle.

How can I optimize my script loops to be faster ?

Don't do any of the above. Look at how other programs such as PIL or
pygame read, store, and paint images.

Here is the script
http://pastebin.com/m652b8d65

tjr

 

[bearophileHUGS]

Jayson Santos:

Hello people, I'm writing a Bitmap parser for study purposes,

This code:

x = 0
y = 0
for line in bmp.bitmap_lines.lines:
for color in xrange(len(line.colors)):
canvas.create_line(x, y, x+1, y, fill="#%02x%02x%02x"
% (line.colors[color].red, line.colors[color].green, line.colors
[color].blue))
x += 1
x = 0
y += 1


May be replaced with something like:

for x, color in enumerate(line.colors):
canvas.create_line(x, y, x+1, y, fill="#%02x%02x%02x" %
(color.red, color.green, color.blue))

And maybe a RGBTriple may be replaced with an immutable namedtuple.
Using nested classes may be overkill for this program.

Use the Python profiler and profile your code with a real image, and
show us/me the profiler results, so I can give you some suggestions to
speed up your code.

Bye,
bearophile

 

[Jayson Santos]

Jayson Santos:

Hello people, I'm writing a Bitmap parser for study purposes,

This code:

        x = 0
        y = 0
        for line in bmp.bitmap_lines.lines:
            for color in xrange(len(line.colors)):
                canvas.create_line(x, y, x+1, y, fill="#%02x%02x%02x"
% (line.colors[color].red, line.colors[color].green, line.colors
[color].blue))
                x += 1
            x = 0
            y += 1

May be replaced with something like:

for x, color in enumerate(line.colors):
    canvas.create_line(x, y, x+1, y, fill="#%02x%02x%02x" %
(color.red, color.green, color.blue))

And maybe a RGBTriple may be replaced with an immutable namedtuple.
Using nested classes may be overkill for this program.

Use the Python profiler and profile your code with a real image, and
show us/me the profiler results, so I can give you some suggestions to
speed up your code.

Bye,
bearophile

Hello bearophile,
Thank you and Terry for your answers.
Here is the new code using your changes http://pastebin.com/m6dfe619d
And here is the profiler http://pastebin.com/m74d282b8

Best Regards
Jayson Reis

 

[bearophileHUGS]

Jayson Santos:

Here is the new code using your changeshttp://pastebin.com/m6dfe619d
And here is the profilerhttp://pastebin.com/m74d282b8

I have suggested you to profile the program mostly for pedagogical
purposes, it's often a good thing to do if you want to speed up a
program. But now it's your job to read the output of the profiler and
try to find where the performance problems are. The profiler output
will be simpler for you to read if you sort lines according to
something better than method name (something like the time used by
functions sounds better) and you tell the profiler to show only the
first few lines.

But a profiler isn't enough, you also need to use the brain. Your code
looks a bit too much OOP So in Java your code may run fast enough,
but in Python it may be too much slow.
The suggestions by Terry are good if you want to speed up your code
signifiantly. Creating a very large amount of objects inside inner
loops a slow thing in Java too, not just in Python. Generally to
create an object you need to allocate memory. Try to write your program
(s) avoiding all or most memory allocations inside the inner loops,
and you will see a big improvement in running speed.

Bye,
bearophile

 

[Jayson Santos]

Jayson Santos:


I have suggested you to profile the program mostly for pedagogical
purposes, it's often a good thing to do if you want to speed up a
program. But now it's your job to read the output of the profiler and
try to find where the performance problems are. The profiler output
will be simpler for you to read if you sort lines according to
something better than method name (something like the time used by
functions sounds better) and you tell the profiler to show only the
first few lines.

But a profiler isn't enough, you also need to use the brain. Your code
looks a bit too much OOP So in Java your code may run fast enough,
but in Python it may be too much slow.
The suggestions by Terry are good if you want to speed up your code
signifiantly. Creating a very large amount of objects inside inner
loops a slow thing in Java too, not just in Python. Generally to
create an object you need to allocate memory. Try to write your program
(s) avoiding all or most memory allocations inside the inner loops,
and you will see a big improvement in running speed.

Bye,
bearophile

Hello bearophile,
Thank you for all, I'm reviewing all my code.
Do I need use some patters or others progamming conventions ?
I tried PIL and PyGame source however they are in C and I can't
understand read and draw functions.
Do you know a python-only image library ?

Best Regards
Jayson

 

[bearophileHUGS]

Jayson Santos:

Do I need use some patters or others progamming conventions ?

That's a strong question...
Knowing OOP well is important, and it's often a good way to program,
etc. But... You may try to rewrite your code with functions only and
no classes (well, you may need to use classes for the TK gui).
Feel free to not follow this suggestion of mine. Even if you follow
it, it will not damage your brain

Bye,
bearophile

 

[Tim Wintle]

Jayson Santos:

That's a strong question...
Knowing OOP well is important, and it's often a good way to program,
etc. But... You may try to rewrite your code with functions only and
no classes (well, you may need to use classes for the TK gui).
Feel free to not follow this suggestion of mine. Even if you follow
it, it will not damage your brain

I'd strongly agree with the above - object creation is overkill in
inner-loops.

Invoking functions and any kind of variable allocation is also going to
slow it down. That's what bearophile's previous comment about accessing
line.colors without the "." lookup by enumerating them was about.

At the end of the day, image manipulation is often better left to C (or
compiled extensions to python in Cython etc.) than done in Python - it's
just too tough to do pointer-magic in Python. You may find that so much
time is being spent by your application in the ".create_line" method
that there's no other option - I'd highly recommend PIL though.


Tim Wintle

 

[Jayson Santos]

Jayson Santos:


That's a strong question...
Knowing OOP well is important, and it's often a good way to program,
etc. But... You may try to rewrite your code with functions only and
no classes (well, you may need to use classes for the TK gui).
Feel free to not follow this suggestion of mine. Even if you follow
it, it will not damage your brain

Bye,
bearophile

Hello bearophile,
Thank you for all.
After changing my code to use only functions instead classes my code
is too much faster.
Here cProfile statistcs:
Using old code : 633608 function calls in 1.361 CPU seconds
Using new code: 475487 function calls in 0.800 CPU seconds

Best Regards
Jayson Reis

 

[bearophileHUGS]

Jayson Santos:

After changing my code to use only functions instead classes
my code is too much faster.
Here cProfile statistcs:
Using old code : 633608 function calls in 1.361 CPU seconds
Using new code: 475487 function calls in 0.800 CPU seconds

If you show a pastebin of the new version (you can also paste it, for
reference for future people, when the pastebin will be deleted),
probably there are ways to improve it more.
And I also suggest you to try Psyco. (Someone recently has shown here
a compiled version for Windows of Psyco for Python 2.6).

Bye,
bearophile

 

[Jayson Santos]

Jayson Santos:


If you show a pastebin of the new version (you can also paste it, for
reference for future people, when the pastebin will be deleted),
probably there are ways to improve it more.
And I also suggest you to try Psyco. (Someone recently has shown here
a compiled version for Windows of Psyco for Python 2.6).

Bye,
bearophile

I'm using linux with python 2.5
Here is the result using psyco.full(): 93 function calls in 0.243 CPU
seconds
And here is the final code: http://pastebin.com/f3e20d669
Bye,
Jayson

 

[bearophileHUGS]

Jayson Santos:

And here is the final code:http://pastebin.com/f3e20d669

Note that if you use Psyco this lookup trick isn't useful, but if the
Psyco isn't available it can improve performance a little:
append = BitmapList['lines'].append


I suggest to replace this code:

red, green, blue = struct.unpack('BBB', s[i:i+3])
append({
'red': red,
'green': green,
'blue': blue,
})

With something just like:

rbg = struct.unpack('BBB', s[i:i+3])

Later you can access r g and b by their position, avoiding the
allocation and creation of a new dict for each pixel.
(array.array too is able to do that, but using unpack is probably fine
too. Using an array.array you can probably decode many rbg triples in
a single time, and slice it later, this looks faster).


In the following code:

if __name__ == '__main__':
...
...
for line in BitmapList['lines']:
for x, color in enumerate(line):
...

note that Psyco is able to compile code only if it's inside functions
or methods, so it may give a bit of improvement if you move such loops
into a function.
I don't know if Psyco is already able to compile enumerate(), if not,
then replacing the enumerate with a manual counter speeds up the code.

I think ShedSkin doesn't have the struct module yet, once someone has
written such standard module, you can probably produce a compiled (C+
+) module with your code that 10-50 times faster than the original
Python code, with no changes in the Python code itself

Bye,
bearophile

 

[Peter Otten]

I'm using linux with python 2.5
Here is the result using psyco.full(): 93 function calls in 0.243 CPU
seconds
And here is the final code: http://pastebin.com/f3e20d669

I think you are heading in the wrong direction. Turning classes into
dictionaries in code that runs just once (like the Bitmap class) makes your
program harder to read, not faster. Adding globals makes it non-reentrant.
You should really concentrate your optimization efforts on the inner loops.
Here avoiding loops written in Python and using tuples instead of a custom
class may offer significant speedups:

def bitmap_line(s):
a = array.array("B")
a.fromstring(s)
return zip(*(iter(a),)*3)

Note that I didn't test or time it because your script requires other
changes to run on AMD64.

Peter