Sorry, an error occurred while loading the content.
Browse Groups

• ## Re: "ocaml_beginners"::[] How to improve test if two boxes are intersected?

(5)
• NextPrevious
• Two other ideas : - it may be faster to interleave the box dimension computation and the validity test, eg. define x0, x1, test x1 = x0, and then only compute
Message 1 of 5 , Aug 15, 2011
View Source
Two other ideas :
- it may be faster to interleave the box dimension computation and the
validity test, eg. define x0, x1, test x1 >= x0, and then only compute y0,
y1 in the favorable case.
- your x0>=0, y0>=0 test is really a validity test on your function inputs:
if a, b are both "valid" (with non-negative coordinates), then those test
can't fail; you could delegate the burden of validity testing to the caller
of the code: it's his job to make sure the parameters valid. In most case
you will probably know statically that the parameters are valid, and skip
the test.
- similarly you could decide to delegate output validity check (x0 >= x1, y0
>= y1) to the receiver of the result; again, in some case you should
statically know that is is correct. This is more risky than the previous
point though, and probably useful in less situations.

Given those considerations, here is how I would write the code for tight
performances, being understood that the function may return invalid output
when given invalid input:

let undefined = {x0 = -1; x1 = -1; y0 = -1; y1 = -1}

let intersection a b =
let {x0=ax0; x1=ax1} = a in
let {x0=bx0; x1=bx1} = b in
let x0 = if ax0 > bx0 then ax0 else bx0 in
let x1 = if ax1 < bx1 then ax1 else bx1 in
if x0 > x1 then undefined
else
let {y0=ay0; y1=ay1} = a in
let {y0=by0; y1=by1} = b in
let y0 = if ay0 > by0 then ay0 else by0 in
let y1 = if ay1 < by1 then ay1 else by1 in
if y0 > y1 then undefined
else {x0; x1; y0; y1}

(Testing would be needed to determine if it's beneficial to delay the
definition of ay0, ay1, by0, by1 to the second case, or if it instead
happens faster is all the memory fetches are located at one place at the
beginning of the function.)

The call site would then check if the return value is == undefined (which is
a global, to allow physical comparison to be used here, and avoid allocating
in the function).

That said, I don't expect significant performance improvements: this would
skip some field fetching, some tests and some allocation, but in practice
this is all quite fast (the field fetched avoided would be in cache anyway,
the tests would be well-predicted, and allocation is just a test plus a
register incrementation in the common case).

On Mon, Aug 15, 2011 at 12:15 PM, Gabriel Scherer <gabriel.scherer@...
> wrote:

> In your function, v is only used in the Some case, but defined (and thus
> allocated) in all cases. I think it would perform better if you only defined
> x0, x1, y0, y1 before the conditional, and built the record only in the Some
> case.
> I also suspect your "imin" and "imax" function do not enable more
> optimization in that case (as the type of bbox_t fields are already
> statically known to be integers), and may even hurt performances if inlining
> doesn't happen. I would suggest using min and max directly, and possibly
> trying to inline their definition.
>
> It's difficult to say more without a directly-compilable
> performance-intensive code example that would allow us to do performance
> measurements. Talking optimization without measurements is usually futile.
>
> It would also help to know in which context this function is used. Is None
> a usual result, or is it an exceptional case (in which case it might be
> better to use an exception or an ugly {-1; -1; -1; -1} value instead of an
> option type, which performs an allocation)? Is it common that the result of
> the intersection is exactly equal to one of the parameters (in which case it
> may be better to add a condition past to test this case, to return the
> parameter without any additional allocation)?
>
>
> On Mon, Aug 15, 2011 at 12:04 PM, Romeyke, Andreas <andreas.romeyke@...
> > wrote:
>
>> Hello,
>>
>> we have a box-datatype defined:
>>
>> (** boundingbox, (x0,y0) means lower left , (x1,y1) upper right edge *)
>> type bbox_t = { x0 : int; y0 : int; x1 : int; y1 : int; }
>>
>> With a profiler we got that result:
>>
>> Counted CPU_CLK_UNHALTED events (Cycles outside of halt state) with a
>> unit mask of 0x00 (No unit mask) count 100000
>> samples % image name symbol name
>> 19808414 19.2089 test.native compare_val
>> 15370569 14.9054 test.native caml_lessequal
>> 11250237 10.9098 test.native camlBbox__intersection_1644
>>
>> As you can see, 10% of time are used for this function:
>>
>> (** processes intersection bbox
>> * @param a bbox a
>> * @param b bbox b
>> * @return tupel to declare if bboxes are connected or intersected or
>> not, the
>> * resulting intersection bbox and the complement set of bboxes
>> * {v
>> * +-+-+-+ +---+ +---+
>> * |r|s|t| |a | |a |
>> * +-+-+-+ | |-+ +-| |
>> * |u|v|w| <=| | | | | | ...
>> * +-+-+-+ +---+ | | +---+
>> * |x|y|z| | b| | b|
>> * +-+-+-+ +---+ +---+
>> *
>> *
>> * v.x0 is max (a.x0 b.x0)
>> * v.x1 is min (a.x1 b.x1)
>> * v.y0 is max (a.y0 b.y0)
>> * v.y1 is min (a.y1 b.y1)
>> *
>> * but only if v.x1 >= v.x0 and v.y1 >= v.y0
>> *
>> * ==> Some v | None
>> * v}
>> *)
>> let intersection a b =
>> (*
>> assert (a.x0 >= 0);
>> assert (a.y0 >= 0);
>> assert (b.x0 >= 0);
>> assert (b.y0 >= 0);
>> assert (a.x1 >= a.x0);
>> assert (a.y1 >= a.y0);
>> assert (b.x1 >= b.x0);
>> assert (b.y1 >= b.y0);
>> *)
>> let v = {
>> x0 = (imax a.x0 b.x0);
>> x1 = (imin a.x1 b.x1);
>> y0 = (imax a.y0 b.y0);
>> y1 = (imin a.y1 b.y1);
>> }
>> in
>> if v.x1 >= v.x0 &&
>> v.y1 >= v.y0 &&
>> v.x0 >= 0 &&
>> v.y0 >= 0
>> then Some v
>> else None
>> ;;
>>
>> The imin() and imax() functions are defined as:
>>
>> let imax (a:int) (b:int) = max a b;;
>> let imin (a:int) (b:int) = min a b;;
>>
>> Did you see any potential to optimize the intersection-function? The
>> caller functions could not be optimized in case of reducing
>> intersection-test :(.
>>
>> Any hints?
>>
>> --
>> Andreas Romeyke
>> - Abteilung Blindenschrift -
>> Deutsche Zentralbücherei für Blinde zu Leipzig (DZB)
>> Gustav-Adolf-Straße 7, 04105 Leipzig
>> Tel: +49 341 7113-..., Fax: +49 341 7113-125
>> Internet: www.dzb.de
>> E-Mail: andreas.romeyke@...
>>
>>
>> [Non-text portions of this message have been removed]
>>
>>
>>
>> ------------------------------------
>>
>> Archives up to December 31, 2010 are also downloadable at
>> http://www.connettivo.net/cntprojects/ocaml_beginners
>> The archives of the very official ocaml list (the seniors' one) can be
>> found at http://caml.inria.fr
>> Attachments are banned and you're asked to be polite, avoid flames
>> etc.Yahoo! Groups Links
>>
>>
>>
>>
>

[Non-text portions of this message have been removed]
• Hello, ... Thanks for your hint, the time spent in this function is decreased from 10% to 7% now. Bye Andreas -- Andreas Romeyke - Abteilung Blindenschrift -
Message 1 of 5 , Aug 15, 2011
View Source
Hello,

Am Montag, den 15.08.2011, 12:15 +0200 schrieb Gabriel Scherer:
> In your function, v is only used in the Some case, but defined (and thus
> allocated) in all cases. I think it would perform better if you only defined
> x0, x1, y0, y1 before the conditional, and built the record only in the Some
> case.

Thanks for your hint, the time spent in this function is decreased from
10% to 7% now.

Bye Andreas
--
Andreas Romeyke
- Abteilung Blindenschrift -
Deutsche Zentralbücherei für Blinde zu Leipzig (DZB)
Gustav-Adolf-Straße 7, 04105 Leipzig
Tel: +49 341 7113-..., Fax: +49 341 7113-125
Internet: www.dzb.de
E-Mail: andreas.romeyke@...

[Non-text portions of this message have been removed]
• Hi Andreas, I had to work with (x,y,z)-aligned boxes recently, albeit not in Ocaml, so I may be able to help you. Could you try the following : let intersects
Message 1 of 5 , Aug 15, 2011
View Source
Hi Andreas,

I had to work with (x,y,z)-aligned boxes recently, albeit not in Ocaml, so I may be able to help you.
Could you try the following :

let intersects a b =
not ((a.x0 > b.x1) || (b.x0 > a.x1)
|| (a.y0 > b.y1) || (b.y0 > a.y1))
;;

let intersection a b =
if intersects a b then
Some { x0 = max a.x0 b.x0; x1 = min a.x1 b.x1;
y0 = max a.y0 b.y0; y1 = min a.y1 b.y1 }
else None
;;

and replace tests like "intersection a b = None" by "not (intersects a
b)" (it avoids building and allocation the new box).

Regards,

Nicolas Braud-Santoni

--- In ocaml_beginners@yahoogroups.com, "Romeyke, Andreas" <andreas.romeyke@...> wrote:
>
> Hello,
> Thanks for your hint, the time spent in this function is decreased from
> 10% to 7% now.
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.