Re: [AD] optimization of create_video_bitmap()

[Robert J Ohannessian <ohannessian@xxxxxxxxxx>]

Sven Sandberg wrote:
> Hello,
> 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 http://home.student.uu.se/svsa1977/tmp/vidopt.zip
> 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
> instructions.).

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.