Performances improvement proposal

[Cerdic]

Hi,
Thanks to all your work on Geometrize!

I'm working on a PHP version of geometrize, based on the Haxe-generated PHP code
https://github.com/Cerdic/geometrize-php with a focus on performance issue as this is in my case a real issue: I plan to compute on the fly low-weight preview svg images as a placeholder for images in web pages.

As a feedback I can point some optimizations I found that are imho applicable to this version:

• Cerdic/geometrize-php@a5d43ec
• Cerdic/geometrize-php@d93ee51
• Cerdic/geometrize-php@a62e45e
• Cerdic/geometrize-php@0a059e2
• Cerdic/geometrize-php@5fbc2bc
• Cerdic/geometrize-php@cca5ccf which then leads to Cerdic/geometrize-php@8535873

The last optimization is a bit tricky and maybe not so interresting for a general use:

I added a rescale() method to shapes Cerdic/geometrize-php@995e206
allowing to start the rendering with a super small thumbnail (ie 64px) and increasing it progressively to 128px, 256px… depending of the final precision I want.

In my case this is a good optimisation as first steps generate large shapes that are slower to compute.

[cancerberoSgx]

Hey! glad to know there's another library port from the haxe code. I'm the author of this JavaScript library generated from haxe code like yours: https://www.npmjs.com/package/geometrizejs

And I'm also concerned about performance and lately giving some thoughts.

I would like to share our experience regarding our libraries and see what we decided or worked differently. I'm describing mine on some aspect and if you can comment on each about yours it would be awesome!

generating the library

Before this, haxe was totally unknown for me. But just in case ask the author if it would be possible to generate JavaScript that could be consumable as a library since he has a web demo but not usable as a library.

@Tw1ddle gently point me out the classes it should be exported and was just a matter of declaring that with annotations and execute the compiler to generate a .js file ready to be used, from node.js or from browser, as an API, using the same names as in haxe project.

how hard / automatic is to re-generate new library versions

In the case of https://www.npmjs.com/package/geometrizejs I focus particularly on

• being able to generate the library automatically without code changes
• expose exactly what the library exposes, if possible without wrapping things so there's no overhead on my part.

Both things were accomplished basically just providing types (TypeScript) for the library API and don't implementing anything (the library actually does not have any implementation). API docs were copy&pasted from haxe code and that could be something the require manual work although there are some tools that could help here too. The library has some tutorials and getting started working examples for node and browser (using js libraries to load the bitmap). Also it has tests that basically verify the happy path and the exporters don't break.

extra code

I wonder if you needed to hack generated code to make it work or use any special compiler flag? or if you change something because of performance ? In case you do, I wonder how do you perform the changes, is it changes on haxe code, or on generated code? or if you use haxe macros to generate different output

performance

I can think on a couple of performance improvements and I'm glad to see is none of your proposals which seems to be related with the primitive algorithm.

It would be awesome to have a PR with yours implemented or better a one PR for each, so we can measure the impact.

One thing I think it can be improved is how Bitmap data is handled.For example:

• in JS at least, bitmap iteration which happens a lot, can be speed up x5 if using a Uint32 instead of Uint8 ( see http://jsfiddle.net/cancerbero_sgx/h824Lq0n/1/)
• and more radically, a setting to minimize bitmap cloning so only happens if really necessary. For example, clone the bitmap on each step to return to the user could be explicitly disabled if he don't care about it or if he is also cloning it...

performance measurement in different language targets

What worries me, and now with a PHP sister, is how to verify that changes that are good for JavaScript don't impact badly in PHP or C++ targets... Since I'm still new with haxe I don't want to start hacking/micro optimizing the code without having a tool to measure the impact on other targets.

So I written this simple application https://github.com/Tw1ddle/geometrize-haxe-unit-tests/tree/performance-lime/tests-performance that's a working haxe program using it as a library, loading/parsing an image to a bitmap, iterating and exporting. I didn't have time to continue but my objectives are:

• that it runs on several targets, at least node.js, browser and C++ (and now PHP)
• write parametrized tests with different option values and bitmap sizes
• report timings for each. The numbers are only meant to personally verify how a change impact on performance of several targets.It's not to compare with past versions / performance budget, etc.

target language custom code

If really important for tuning performance probably we will need to change the target language code that haxe compiler actually generates. For example, in JavaScript instead using an array use an ArrayBuffer or typed array for bitmaps. or iterate differently in js than in others, or use a native library that performs X algorithm optimally in JS. Or do some processing with the gpu !. etc.

I'm just curious about how or if haxe solve this problem and recommendations. How the code would look like having macros/injections for several languages in arbitrary parts ?

Opinion about the API

The library is simple and focus on what it should and don't have dependencies. But could be hard to use since users are responsible parsing/loading images, implementing the step iterations. But IMO this is OK and these feature should not be supported.

I do think there could be other libraries on top of it that solve these problems, but independently. In my case I made a command line tool that exposes the API and supports some image formats, implements the iterations given by the user and exports to a file in a format the user wants.

Now I'm working on migrate these as an -extra project that provides API for this and add more APIs, besides mentioned, being able to control the iteration loop.

A problem I see is it lacks with docs to get started / or minimal working examples / guidelines. I would also like to work on this area, when I feel more comfortable with haxe technology.

Again I would love to hear your experience / thoughts on these. Sorry for the long comment, Thanks!

[Tw1ddle]

Hi @Cerdic - low-weight preview SVGs should be a good use case for this! In case it's a useful reference, I believe this library can do something similar for previews: https://github.com/axe312ger/sqip

Jose M Perez also wrote a good article about placeholder SVGs a few years back if you haven't seen that: https://www.freecodecamp.org/news/using-svg-as-placeholders-more-image-loading-techniques-bed1b810ab2c/

As @cancerberoSgx pointed out, it'd be useful to have a benchmark that compare performance across different targets.

Some people took interest in using this library with the php target a few years ago, but they didn't like the generated code and performance. I gather it's harder to use platform-specific defines/#if/#else blocks to get around that, compared to other targets like js. So I think your approach of editing the generated code directly is probably the best way to optimize.

I'll take a look at the improvements you made, appreciate the feedback. Let us know how you apply the project, it would be nice to add a links in the readme if you create a site or app using such previews 😄

[Cerdic]

@cancerberoSgx just like you I never heard about Haxe before digging in that project and juste discovering the entire ecosystem.

In fact at the begining my idea was also to work on the Haxe version and use the code generation to get a working PHP version.

But, even if things are not fully decided yet as I only did a small start in the PHP refactoring, I'm more and more thinking to really fork for a real full PHP lib.

This is really annoying for the long term maintenance because of course meaning that the future improvements in geometrize-haxe will have to be reported manually.
But I can't see how i would be able to keep the link with the source geometrize-haxe, as well as

• for the PHP code readibility : the generated PHP code is way too far from reaching usual PHP standards for a distributable PHP lin usable in other projects (such as via composer)
• for performance reasons : the PHP version is relying on a lot of Haxe structures (for Math, random, arrays…) instead of using the native PHP data structures, which is not super efficient

The performance thing is really an issue for my use case, and I think this will also need fine tuning, which is here totaly dependant of the language

But sharing some unit test would be great, I can agree with that! :)

[Cerdic]

@Tw1ddle thank you for the feedback. I know the sqip tool and the article from Jose M Perez which is my inspiration source. SQIP is not a solution for me as for security reasons I can not rely on an external binary tool, and neet a full PHP implementation.

So I was really happy to be able to use the geometrize-haxe PHP generated code as a first version that allows me to test the concept and check that it is possible to reach a fast enough generation speed to get something usable.

At the moment a 75 triangles SVG generation from a real life JPEG image is consuming something around 15 to 18s.
This is still a lot but manageable:

• by splitting the full process in several rounds (the first display only shows some triangles, and the preview is refined at each display to reach the final 75triangles that match my SVG size budget)
• by use of caching: once the preview is fully processed it is cached and store "forever" (at least as long as the source image doesn't change)

And I have good hope to imprive this computing time by some more optimisations.

At the moment this is a work in progress, on a development website not yet visible in a real lif, but I will of course point you as soon it is visible somewhere.

[cancerberoSgx]

At the moment a 75 triangles SVG generation from a real life JPEG image is consuming something around 15 to 18s.

this sounds too much, how big is the input image ? what values for runner options are you using ? Could you share the steps iterations code ? Maybe you are doing something unnecessary there. I general you just need to store each step result and only build the svg after iteration finish.

I was looking at your library and seems the generated code did take care of using some PHP native structures (unlike in js that translation is almost straightforwards from haxe code) so my guess was it should be faster than js'. But those numbers are much slower.

[Cerdic]

@cancerberoSgx some more details

About measurment:

• this number is what I get on my development computer, so not using a fully optimised PHP
• on the same computer, the native OS X Primitive.app takes 3s for a 75 triangles shaping of the same image, and the online geometrize-haxe demo https://www.samcodes.co.uk/project/geometrize-haxe-web/ about 5s (with exactly the same rendering settings)
• on a real production server, with optimized PHP (which mainly means using opcode cache in addition), the computing time goes down to 5s

About settings:

• these are here https://zone.spip.net/trac/spip-zone/browser/spip-zone/_plugins_/adaptive_images/trunk/preview/image_geometrize.php#L32
• I'm starting the first 20 steps of rendering on a 65px width thumbnail (generated from my source image) for speed reason (first iterations are the slower because producing large shapes) then switching to a 129px thumbnail width to get more precision for the next steps until 75
• the steping process is just a single loop https://zone.spip.net/trac/spip-zone/browser/spip-zone/_plugins_/adaptive_images/trunk/preview/image_geometrize.php#L103 (if you except the resizing occuring once after 20 steps, but this is a global win), and I'm exporting the SVG only at the end

[cancerberoSgx]

I'd try candidateShapesPerStep ==50 and experiment what's an acceptabe trade off . and perhaps in php you could do the resize and all extra things inside the loop in a different thread ? (something is not possible or easy in js) i wonder how big is the input bitmap . It 'd be interesting to compare these numbers with a C++ version too... my two cents

[Cerdic]

FYI I was able to cut the computing time by about a half by replacing all Haxe structures like _hx_array() with native PHP arrays and using native PHP cloning instead of the haxe hclone() methods.

This makes me now sure that the PHP version is definitively a fork :(

With some other slight improvements, refactoring and an interresting algorithm improvement on random shapes #22 I can now reach the 100 triangles shaping in 1 to 1.5s on the production serveur, which is much better

[cancerberoSgx]

I'm playing to learn haxe in my own project , https://lib.haxe.org/p/bitmap/ taking some concepts from here. I've noticed that is faster to clone bitmaps by using bites.sub() / bytes.blit() (that should use the native array copy() method. Also I'm making Sure.sure() statements optional for critical operations like get/set pixel and also for this project I would do in Util. I'm taking notes to later contribute to this project.

[francescoagati]

inline code should help for performance and also force inline di haxe 4

[francescoagati]

and also convert typedef in classes and use structinit for mutate php array map in real classes