Looking at memory allocaters (specifically the recyclingAllocator), I noticed that GIF2.cpp allocates in one go, three blocks of fixed size, and releases them at the same time. So these could also be allocated as one block: 535 if (!gs->prefix) 536 gs->prefix = (PRUint16 *)gif_calloc(sizeof(PRUint16), MAX_BITS); 537 if (!gs->suffix) 538 gs->suffix = ( PRUint8 *)gif_calloc(sizeof(PRUint8), MAX_BITS); 539 if (!gs->stack) 540 gs->stack = ( PRUint8 *)gif_calloc(sizeof(PRUint8), MAX_BITS); and: 1081 gif_free(gs->prefix); 1082 gif_free(gs->suffix); 1083 gif_free(gs->stack); Allocating them as one block, saves some memory allocation overhead, also in the recycler (or even more so!). Instead of 3 blocks of different sizes per decode run, it allocates always one block of the same size per run.

Well, could we go even further and make them static member of gif_struct ? Current life span : - GIFInit : gs is allocated - first call to 'gif_write' : those static size buffers are allocated - gif_destroy : gs and the buffers (if present) are disallocated Will usually GIFInit be called without gif_write being called too soon afterward ? Of course, that change would need a more careful review than the obvious change above.

Merged the allocation of GIFStruct and the prefix/suffix/stack buffers, also moved this allocation to nsGIFDecoder, so both allocation and free of the GIFStruct is in one file. Further, some small cleanups and optimisations in GIF2.cpp. Sideeffect: some codesize reduction about 700bytes. Note, it is not clear whether the memset's all required for the prefix/suffix and stack buffers, but I left them in to be safe.

Comment on attachment 168690 [details] [diff] [review] Merged allocation of GIFStruct and the prefix/stack/suffix + memset(gs->prefix, 0, sizeof(PRUint16)*MAX_BITS); + memset(gs->suffix, 0, sizeof(PRUint8)*MAX_BITS); + memset(gs->stack, 0, sizeof(PRUint8)*MAX_BITS); How about using sizeof(gs->prefix) etc there in stead of hard coding the sizes here too? + PRBool is_transparent; /* TRUE, if tpixel is valid */ + PRBool is_local_colormap_defined; + PRBool progressive_display; /* If TRUE, do Haeberli interlace hack */ These are asking to be changed to PRPackedBool's. +/***************************************************************************** ** + * Gif decoder allocator + * + * For every image that gets loaded, we allocate + * 4097 x 2 : gs->prefix + * 4097 x 1 : gs->suffix + * 4097 x 1 : gs->stack + * for lzw to operate on the data. These are held for a very short interval + * and freed. This allocator tries to keep one set of these around + * and reuses them; automatically fails over to use calloc/free when all + * buckets are full. That's not exactly true any more, no more separate allocations etc. Update the comment. With that, r=jst.

Note, the free of mGIFStruct in ::Close was missing, so I've added it there. So save more code bytes, the destructor now calls ::Close (which is save to do), and some other small assembly level optimisations in GIF2.cpp. Fully tested with a wide range of GIF files, very large ones, 'truecolors', very large interlaced files, etc.

Comment on attachment 168765 [details] [diff] [review] Incorporated comments from jst. >Index: modules/libpr0n/decoders/gif/GIF2.cpp >+const PRUintn kDup[] = { 0, 7, 3, 1 }; >+const PRUintn kRowInc[] = { 0, 8, 8, 4, 2 }; >+const PRUintn kRowTop[] = { 0, 4, 2, 1, 0 }; can you add a comment for these? >Index: modules/libpr0n/decoders/gif/nsGIFDecoder2.cpp >+ if (!gGifAllocator) >+ gGifAllocator = new nsRecyclingAllocator(kGifAllocatorNBucket, >+ NS_DEFAULT_RECYCLE_TIMEOUT, "gif"); >+ mGIFStruct = (gif_struct *)(gGifAllocator ? >+ gGifAllocator->Calloc(sizeof(gif_struct),1) : >+ calloc(sizeof(gif_struct),1)) If |new nsRecyclingAllocator| failed, why do you bother trying to call |calloc|? I don't understand. It seems like you would have an OOM condition, and would just want to bail. Surely calloc will also fail, no? I think this patch should also be reviewed by one of the ImageLib peers, preferrably by pavlov.

This version incorporates comments from Darin: * Added comments to the constant arrays * I left in the 'calloc' bailout, because it doesn't hurt, and can be be backup for the RecyclingAllocator... I've added the following changes: * removed some unused states from the gif decoder, merged the gif header parsing into one state. * changed BlockAllocCat to keep the 'hold' size a multiple of 256 bytes, and to only resize when it needs to be bigger (it will be at most 1024 bytes anyway). This saves a malloc and realloc for each 4096 byte crossing (because GifWrite gets 4K bytes per call), and even for very large animated gifs, now at most one malloc and one realloc is needed. This makes the loading of those gifs much faster. (memory usage is still bad because of the 24bit color processing...) * Renamed functions to be more consistent (GifInit, GifWrite, GifClose) * Removed gif_write_ready, because it is not needed anymore because of the streaming (4K per call), and because the parser is not limited to the buffer size anyway.

> * I left in the 'calloc' bailout, because it doesn't hurt, and can be be backup > for the RecyclingAllocator... on the contrary, it increases codesize even though it will practically never be used. seems like a bad choice to me. be careful about adding more complexity to this patch. it increases the barrier to code review.

Comment on attachment 168941 [details] [diff] [review] Incorporated comments from Darin, and more malloc optimisation. See latest patch for the review!

Comment on attachment 169278 [details] [diff] [review] Per darin's comment, removed the fallback to 'calloc' GIF2.h:114 int ipass; /* Interlace pass; Ranges 1-4 if interlaced. */ Please modify this comment to explain 0 is non-interlaced. + /* Do we already have enough data in the accumulation + buffer to satisfy the request ? (This can happen + after we transition from the gif_delay state.) */ This comment refers to a const that has been removed. The memory allocation stuff will take me a bit longer to digest. Ultimately pav will have to decide whether it's wise to remove netscape extension #2. While I don't fully understand it myself, wouldn't it be possible right now for a GIF to request that all its data be available before the images is decoded? Without the extension, the gif author would lose that ability. Please correct me if I misinterpreted what this extension is accomplishing.

Thanks for the review sofar. I've assimilated the first two comments. About the Netscape extension: I've had a lot of thought and research on this. It seems that there are no GIF images at all using this. Furthermore, the extension is very rarely described. No image creation applications are using this. But the most important reason to remove it, is that it is 'unsafe'. One can add this extension to an image, requesting a very large 'read-ahead' (say about 2GB), which then is all allocated and tried to filled from the stream, which may cause problems in the application (and even OS). So, this is a very strong case to remove it. It is not used, doesn't have any visible impact, and can cause 'buffer overflow / memory overflow', when the extension is misused.

I don't think we want to remove the netscape extension support.

Comment on attachment 171477 [details] [diff] [review] Incorporated comments from ArronM Aaron, could you review this and let us know if you feel it might be too risky to take right now as we're nearing the end of the 1.8 cycle?

Comment on attachment 171477 [details] [diff] [review] Incorporated comments from ArronM The sheer size and amount of changes the patch has is reason enough to say it's definitely not for 1.8. -r due to pavlov's comments.

I can agree with postponing it after 1.8. However I don't agree with the Netscape extension. To make the earlier argument against this extension more clear: using this extension, one can easily create a GIF image with a request to buffer upto 4GB bytes before decoding it. This means that the GIF decoder will never end the decoding, and tries to build up an holding buffer of that size. I have not yet tested this, but it is very likely that this will surely crash the application. Furthermore, the net effect of this extension is gone, because of the streaming towards the decoder. There is no usefull effect of it, and no image creation program can produce this extension. It is not a standard extension, and only documented as being proposed by Netscape around version Netscape 2.1, but it is never formally released. So, normally when it doesn't harm, we would leave such backwards compatibility things such as this 'netscape extension' in. However, it can do serious harm, so let's remove it.

>I have not yet tested this, but it is very likely that this will surely crash >the application. that would be a bug. mozilla should not crash if a memory allocation fails.

Compile and run this. It takes an c:\tmp\error.gif and creates an c:\tmp\error2.gif with the NETSCAPE2.0 wait_for_fullness extension inserted.

I have tested the support of the NETSCAPE2.0 extension with the old code and the new code. Luckely it doesn't crash mozilla but mozilla won't display the image either. With the new code, mozilla is able to correctly read, parse, and display the image. IE, IrfanView, PaintshopPro can all load the extended gif image, but mozilla/firefox refuses to display it at all (it does not even 'broken image' ) Further analysis of the code confirms me that the extension is not supported at all, it doesn't work, and prevents the otherwise valid image to display. So, let's remove something which is not working anyway, and prevent issues later with this extension. Anyway I didn't really remove it, I only changed it into a 'NOP'. So, requesting re-review, as all other comments have been incorporated.

Comment on attachment 171477 [details] [diff] [review] Incorporated comments from ArronM Even not for 1.8, let's still review it.

Comment on attachment 171477 [details] [diff] [review] Incorporated comments from ArronM I agree it should be reviewed, but not by me. This is definitely more of a Stuart review, since he has concerns about the extension, and knows more about the decoding process than I do. Re-assigning review :)

Added bug 105370 to the 'block' list, as the identified MLK (the calloc at GIF2.cpp:1017) is fixed with this patch as well.

This patch saves even more code (now in total more than 5K on a windows optimized build for just the GIF decoder). The main difference with the last one, is that the whole 'gather' construct is replaced with one 'hold' buffer of fixed size (3*256 bytes), and that instead of increating the gathering in state engine, the entry and exit points of GifWrite take care of 'hold' buffer, as the only function is to move not yet parsed bytes from one GifWrite call to the next. This also speeds up the parsing as in the old case between each state, the gather_state was called upon, and now the state engine directly switches from gif_image_header to the next valid state, if there are enough bytes in the buffer. If not the remaining bytes are put in the hold, awaiting the next call to GifWrite. Also merged consume_comment with skip_block, as they did the same thing: skipping the blocks... Tested with a wide range of static and animated gif files (upto 6MB).

To stress the importancy of this patch: * Not only it saves code and footprint, but it also speeds up the loading of large animated GIFs. * But even more importantly it reduces 7 dynamic allocated (and often reallocated buffers to 3 (rowbuf, global_colormap and local_colormap) once allocated per image (possibly enlarged for next frames). * Even more: each GifWrite caused in the old situation at least one malloc and one realloc for the 'gathering', now it is only one static buffer. * Even more: local_colormap is now only allocated once and only enlarged when needed for all frames within an animation. So, this reduces memory fragmentation a lot, and even reduces the change on MLK's. With the old code it does seem to happen sometimes (bug 105370).

Comment on attachment 175330 [details] [diff] [review] Updated version, using fixed buffer of holding block between GifWrite's Moved review request to latest patch version.

Additional changes: * Now also global_colormap is a fixed buffer, and directly copied into from the input stream (saves copy through hold buffer) * Also local_colormap is directly assembled in its (dynamically allocated) colormap * Remove BackgroundColor as it isn't used at all * Optimized same function signatures Some statistics: Before Alloc4 Startup 8 allocs, 17424 bytes 4 allocs, 17628 bytes Loading dir: 119 allocs, ± 17500 bytes 16 allocs, ±17700 bytes per image Loading aniGif.gif: 40 allocs, 17509 bytes 4 allocs, 17843 bytes Loading tholen.gif 37 allocs, 19285 bytes 3 allocs, 19234 bytes Note: Each alloc also some overhead, so the actual memory usage is much more In summary, each GIF decoding now takes at most 4 allocs (not counting the allocations by gfxImageFrame and imgContainer), instead of 8 + 2*number_of_4K_input_stream_crossings + number_of_frames. Some time measurements: Before Alloc4 Startup (loading throbber.gif): 21 6 Loading techno_moogle_dance_party_by_the_darkmoogle.gif: 1748 1291 Loading galaxy_anim_short.mov2.gif: 237537 218299 Note, measured with PRTimeInterval on WinXP, so numbers are in itself meaningless, but the difference is interesting: between 10% and 30% faster image decoding.

Comment on attachment 175923 [details] [diff] [review] Even more memory and code size optimization Moving review request to latest patch version. See also the included benchmark data between the old situation and the latest patch version.

Comment on attachment 175923 [details] [diff] [review] Even more memory and code size optimization You're combining too many changes into a single patch. Mozilla's gif decoder has been battle hardened by years of exposure, so we take changes to it pretty seriously. A patch doing lots of unrelated changes makes it hard to give a full review. Please split your work into logical stages.

Reverted to the level of 2005-01-17, as reviewed by Darin and ArronM. This one should be 'easier' to review.

Comment on attachment 175938 [details] [diff] [review] Do only the malloc optimisation. This version of the patch still combines your allocation changes with modifications to the state machine and other miscellaneous code tweaks. While we like code cleanup, it should be seperated from other changes. Please don't feel as though you're being singled out for these sort of comments; new mozilla contributors often run into this. Unfortunately the mozilla review process generates a bit of a viscious cycle - reviews take a while, so contributors want to put more into their patch to reduce the number of reviews they need to chase, which slows the review, etc...

This version only contains the following malloc changes: * stack, prefix and suffix of the lzw decoding from alloc to array as part of gif_struct * Moved RecyclingAllocator from gif2.cpp to nsGIFdecoder.cpp where it used for the full gifstruct allocation, instead of three items stack, prefix and suffix. * global_colormap as an array part of gif_struct: is always used, and never larger than 768 bytes. * mRGBLine and mAlphaLine: only REALLOC when it needs to be bigger instead of always (generally it will be same or smaller (first frame is generally the largests)). * Remove 'request_buffer_fullness' as it doesn't work (image will not show up, and see testcase above, and can potentially generate a very large memory allocation (as large as the full image source file). * Removed unused member 'control_extension' (only set once, never used). * Changed a few bools into PRPackedBools (as asked by jst)

Comment on attachment 176044 [details] [diff] [review] Two dirty patch lines removed... >--- modules/libpr0n/decoders/gif/GIF2.cpp 9 Jun 2004 18:36:25 -0000 1.51 >+++ modules/libpr0n/decoders/gif/GIF2.cpp 2 Mar 2005 15:40:49 -0000 >+ // Clear out the structure, excluding the arrays >+ memset(gs, 0, (int)((char*)&((gif_struct*)0)->stack) ); Include stddef.h and use "offsetof(gif_struct, stack)". >@@ -406,20 +422,17 @@ > { > nsGIFDecoder2* decoder = NS_STATIC_CAST(nsGIFDecoder2*, aClientData); > PRUint32 bpr, abpr; >+ > // We have to delay allocation of the image frame until now because >- // we won't have control block info (transparency) until now. The conrol >+ // we won't have control block info (transparency) until now. The control > // block of a GIF stream shows up after the image header since transparency > // is added in GIF89a and control blocks are how the extensions are done. > // How annoying. > if(! decoder->mImageFrame) { >- gfx_format format = gfxIFormats::RGB; >- if (decoder->mGIFStruct->is_transparent) { >- format = gfxIFormats::RGB_A1; >- } >- > #if defined(XP_WIN) || defined(XP_OS2) || defined(XP_BEOS) || defined(MOZ_WIDGET_PHOTON) >- // XXX this works... >- format += 1; // RGB to BGR >+ gfx_format format = decoder->mGIFStruct->is_transparent ? gfxIFormats::BGR_A1 : gfxIFormats::BGR; >+#else >+ gfx_format format = decoder->mGIFStruct->is_transparent ? gfxIFormats::RGB_A1 : gfxIFormats::RGB; > #endif > > // initalize the frame and append it to the container Remove this chunk from your patch.

Added the use of 'offsetof' (much nicer indeed), and remove the patch chunk fixing the typo and the 'XXX this works' thing.

Comment on attachment 176122 [details] [diff] [review] Comments from tor incorporated Note, the removal of '#include "prtypes.h" was not intentional, but it compiles and work, but may be other platform will still require it?

Comment on attachment 176122 [details] [diff] [review] Comments from tor incorporated >+ PRUint8 stack[MAX_BITS]; /* Base of decoder stack */ >+ PRUint16 prefix[MAX_BITS]; >+ PRUint8 suffix[MAX_BITS]; >+ PRUint8 global_colormap[3*MAX_COLORS]; /* Default colormap if local not supplied, 3 bytes for each color */ Since MAX_BITS is odd, for maximum packing this should be reordered prefix, global_colormap, stack, suffix (flip last two to taste), with the appropriate corresponding change to GIFInit. sr=tor with that change. Add -p to your diff options in the future.

Changed order of arrays to: prefix, suffix, stack and global_colormap, as prefix is the only one with even size, others are all odd.

Checking in GIF2.cpp; /cvsroot/mozilla/modules/libpr0n/decoders/gif/GIF2.cpp,v <-- GIF2.cpp new revision: 1.52; previous revision: 1.51 done Checking in GIF2.h; /cvsroot/mozilla/modules/libpr0n/decoders/gif/GIF2.h,v <-- GIF2.h new revision: 1.20; previous revision: 1.19 done Checking in nsGIFDecoder2.cpp; /cvsroot/mozilla/modules/libpr0n/decoders/gif/nsGIFDecoder2.cpp,v <-- nsGIFDecoder2.cpp new revision: 1.65; previous revision: 1.64 done Checking in nsGIFDecoder2.h; /cvsroot/mozilla/modules/libpr0n/decoders/gif/nsGIFDecoder2.h,v <-- nsGIFDecoder2.h new revision: 1.25; previous revision: 1.24 done

Code is committed and verified to be working as designed

Good Job, Alfred Kayser.