Hello Sean,
> On 15 Aug 2017, at 16:30, Christopher Sean Morrison <brl...@mac.com> wrote:
>
>
> Marco,
>
> Interesting -- can you elaborate on what this patch is doing (or supposed to
> be doing)? I'm not fully following what the old code was doing. Obviously
> looks like it's just finding the first unmasked / region set in the bitfield,
> but I'm not 100% sure that's all that is going on.
To give some context, I am currently cleaning and refactoring the code to
prepare a ticket with the OpenCL CSG boolean evaluation code, to possibly merge
with the trunk. And I noticed that we could just cache the first region index
during boolean evaluation and pass it directly to the
rt_default_multioverlap(), which avoids having to search for the first set bit
in the regiontable bitfield, and that could be a problem for very sparse
bitfields.
>
> On the surface, patch seems like an optimization to skip iterating twice.
> Yes? It would be interesting to know if the C code would benefit (and
> operate identically) if the same patch is applied -- have you / can you test
> that? Just applying the patch and running benchmark before/after should be
> adequate.
>
This is actually an approach to replicate what the C code does. The C code uses
a list to store the regions involved in each partition, and in the
rt_default_multioverlap(), the first region in the regiontable is directly
accessed:
[-
lastregion = (struct region *)BU_PTBL_GET(regiontable, 0);
-]
So in theory, applying this patch in the C code shouldn’t have any impact in
the results, as the first region is already being directly accessed.
Cheers!
Marco
> It does have the potential to change results, so it's worth a quick test.
>
> If this is a direction we want the code to go, I'll have to send out some
> announcements because rt_default_multioverlap() is public API subject to
> change policy. Fortunately this change is minimally impacting. We'll have
> to sort out how the OpenCL side will binds to third-party apps later too
> since it looks like that calling pattern must change.
>
> Cheers!
> Sean
>
>
>
>
>
> On Aug 15, 2017, at 09:42 AM, mdtwenty--- via brlcad-commits
> <brlcad-comm...@lists.sourceforge.net> wrote:
>
>> Revision: 70080
>> http://sourceforge.net/p/brlcad/code/70080
>> <http://sourceforge.net/p/brlcad/code/70080>
>> Author: mdtwenty
>> Date: 2017-08-15 13:42:51 +0000 (Tue, 15 Aug 2017)
>> Log Message:
>> -----------
>> passing first region index to overlap handler
>>
>> Modified Paths:
>> --------------
>> brlcad/branches/opencl/src/librt/primitives/bool.cl
>>
>> Modified: brlcad/branches/opencl/src/librt/primitives/bool.cl
>> ===================================================================
>> --- brlcad/branches/opencl/src/librt/primitives/bool.cl 2017-08-14
>> 19:17:24 UTC (rev 70079)
>> +++ brlcad/branches/opencl/src/librt/primitives/bool.cl 2017-08-15
>> 13:42:51 UTC (rev 70080)
>> @@ -763,32 +763,17 @@
>>
>> void
>> rt_default_multioverlap(global struct partition *partitions, global struct
>> bool_region *bregions, global uint *regiontable,
>> - const uint pp_idx, const uint total_regions, const uint
>> headpp_idx, const size_t id)
>> + const uint first_region, const uint pp_idx, const uint
>> total_regions, const uint headpp_idx, const size_t id)
>> {
>> global struct bool_region *lastregion;
>> - int code, ret;
>> + int code;
>>
>> uint rt_index = total_regions/32 +1;
>> uint lastregion_id;
>>
>> // Get first region of the regiontable
>> - for (uint i = 0; i < rt_index; i++) {
>> - uint mask = regiontable[id * rt_index + i];
>> - ret = 0;
>> - while (mask != 0) {
>> - uint lz = clz(mask);
>> - uint k = (i * 32) + (31 - lz);
>> - if (isset(regiontable, id * rt_index, k) != 0) {
>> - lastregion = &bregions[k];
>> - lastregion_id = k;
>> - ret = 1;
>> - break;
>> - }
>> - // clear bit in mask
>> - mask &= ~(1 << (31 - lz));
>> - }
>> - if (ret) break;
>> - }
>> + lastregion = &bregions[first_region];
>> + lastregion_id = first_region;
>>
>> /* Examine the overlapping regions, pairwise */
>> for (uint i = 0; i < rt_index; i++) {
>> @@ -886,6 +871,7 @@
>> //iterate over partitions
>> for (uint current_index = head; current_index != UINT_MAX; current_index =
>> partitions[current_index].forw_pp) {
>> global struct partition *pp = &partitions[current_index];
>> + uint first_region_idx = UINT_MAX;
>>
>> claiming_regions = 0;
>> /* Force "very thin" partitions to have exactly zero thickness. */
>> @@ -930,6 +916,9 @@
>> uint k = (i * 32) + (31 - lz);
>> if (isset(regiontable, id * rt_index, k) != 0) {
>>
>> + if (first_region_idx == UINT_MAX)
>> + first_region_idx = k;
>> +
>> if (bregions[k].reg_all_unions) {
>> claiming_regions++;
>> lastregion_idx = k;
>> @@ -951,7 +940,7 @@
>>
>> if (claiming_regions > 1) {
>> /* There is an overlap between two or more regions */
>> - rt_default_multioverlap(partitions, bregions, regiontable,
>> current_index, total_regions, head, id);
>> + rt_default_multioverlap(partitions, bregions, regiontable,
>> first_region_idx, current_index, total_regions, head, id);
>>
>> /* Count number of remaining regions, s/b 0 or 1 */
>> claiming_regions = 0;
>>
>> This was sent by the SourceForge.net <http://sourceforge.net/> collaborative
>> development platform, the world's largest Open Source development site.
>>
>>
>> ------------------------------------------------------------------------------
>> Check out the vibrant tech community on one of the world's most
>> engaging tech sites, Slashdot.org <http://slashdot.org/>!
>> http://sdm.link/slashdot <http://sdm.link/slashdot>
>> _______________________________________________
>> BRL-CAD Source Commits mailing list
>> brlcad-comm...@lists.sourceforge.net
>> <mailto:brlcad-comm...@lists.sourceforge.net>
>> https://lists.sourceforge.net/lists/listinfo/brlcad-commits
>> <https://lists.sourceforge.net/lists/listinfo/brlcad-commits>
> ------------------------------------------------------------------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, Slashdot.org!
> http://sdm.link/slashdot_______________________________________________
> BRL-CAD Developer mailing list
> brlcad-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/brlcad-devel
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
BRL-CAD Developer mailing list
brlcad-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/brlcad-devel
