Re: [AD] optimization of create_video_bitmap()

[ Thread Index | Date Index | More Archives ]

Sven Sandberg wrote:
The attached patch optimizes create_video_bitmap(). The old version
has a worst case of O(n^3), where n is the number of already existing
video bitmaps, and it seems that this cubic behavior is realized in
quite normal circumstances. The new version is O(n^2) in worst case,
and seems to be more like linear under normal circumstances. This
means that it's much faster to allocate many bitmaps, but the
improvement is smaller for few bitmaps. E.g., allocating a grid of
32x24 video bitmaps is 2300 times faster on my machine. I uploaded
my test program to
in case anyone is interested (Requires cvs version of adime; sorry
for this but it was much easier for me. See top of C file for

I'll take a look at it tonight. AllegroGL uses a O(h * n^2) algorithm for doing something similar (optimizing texture space for glyphs), where 'h' is the height of the texture in pixels. Perhaps I can backport this algorithm to AllegroGL, or merge some ideas in between both algorithms.

Mail converted by MHonArc 2.6.19+