January 16, 2021
On Saturday, 16 January 2021 at 17:03:41 UTC, Bruce Carneal wrote:
> Converting over:
> 	uint32 mask = -int32(f >> 31) | 0x80000000;
> 	return f ^ mask;
> and back:
> 	uint32 mask = ((f >> 31) - 1) | 0x80000000;
> 	return f ^ mask;

Thanks, this is the same I have as option 1 above.

> This form is branchless and is easily (SIMD) vectorized.

Yes, and perhaps also better for the CPU pipeline.

> split, ordering.  For my current work I prefer this to traditional float behavior and find it a useful bijection overall.  YMMV.

Out of curiosity, what do you need to sort floats for?

January 17, 2021
On Saturday, 16 January 2021 at 19:43:53 UTC, Ola Fosheim Grøstad wrote:
> On Saturday, 16 January 2021 at 17:03:41 UTC, Bruce Carneal wrote:
>> Converting over:
>> 	uint32 mask = -int32(f >> 31) | 0x80000000;
>> 	return f ^ mask;
>> and back:
>> 	uint32 mask = ((f >> 31) - 1) | 0x80000000;
>> 	return f ^ mask;
>
> Thanks, this is the same I have as option 1 above.

Almost certainly the same.  Only the most aggressively stupid compiler modes would forego an available/advantageous conversion of the subtract to a mono-operand negation.  Even then, once any loop got rolling throughput should be identical.  Yes.

>
>> This form is branchless and is easily (SIMD) vectorized.
>
> Yes, and perhaps also better for the CPU pipeline.
>

Unless the data you're dealing with is nearly sorted, the branch mispredict penalty could really hurt so, yeah, don't go there.

For the branchless variant, throughput will come down to issue capability.  For a dual issue SIMD CPU it looks like a naive loop should hit throughput of 2 SIMD vectors every three cycles (I don't have real numbers for the standalone case, all my transforms appear within larger basic blocks).  SIMT throughput should be memory subsystem limited.

>> split, ordering.  For my current work I prefer this to traditional float behavior and find it a useful bijection overall.  YMMV.
>
> Out of curiosity, what do you need to sort floats for?

I've been working on my current project for a few months but I'm still not ready to talk about it in detail.  I will say that it does not sort anything (doesn't have the power/compute budget for sorting) and that it does employ the bijection as a type erasure/restoration mechanism.

January 17, 2021
On Sunday, 17 January 2021 at 04:03:30 UTC, Bruce Carneal wrote:
> I've been working on my current project for a few months but I'm still not ready to talk about it in detail.  I will say that it does not sort anything (doesn't have the power/compute budget for sorting) and that it does employ the bijection as a type erasure/restoration mechanism.

This "bijection" strategy is interesting.  (I assume you think of bijective functions in mathematics?) For some reason I've never really given it much thought. But it makes a lot of sense for encoding keys. Some online services also only accept keys that are either strings or 64bit integers, so it might be useful in other contexts.

I've written a generic key type that does this encoding (in C++, but easy to port to D), and are working on a compressing one. So, for instance if you have a tuple of (z,y,x) then you can specify that 1≤x≤31, 1≤y≤12, 1970≤z≤2030 and let it be compressed either by bit shifting or multiplication (slower but tighter). So for instance (2021,1,17) would compress as

((2021-1970)*12+0)*31+16

Is there some way to find out the range (min, max) of an enum?

The next step is to cover keys larger than 64 bits, I guess I should cover up to 256 bits.


January 17, 2021
On Sunday, 17 January 2021 at 10:37:10 UTC, Ola Fosheim Grøstad wrote:
> On Sunday, 17 January 2021 at 04:03:30 UTC, Bruce Carneal wrote:
>>
>
> This "bijection" strategy is interesting.  (I assume you think of bijective functions in mathematics?)

Yes, one-to-one and onto (and we've wandered quite a ways OT).  Good luck.

1 2 3 4 5 6
Next ›   Last »