On 03/29/2012 01:30 PM, John Cowan wrote:
> I wasn't speaking of an atomic instruction, but of the fact that to set one
> or more bits in a byte, you have to read the byte, modify it, and write it
> back.  This is far more expensive than setting all the bits in a byte,
> which is just a write.

That seems unlikely: Regardless, you have to read the whole cache line,
and the cost of the memory-to-cache transfer should swamp the cost
modifying a cache line.  If you're modifying multiple bits then
a compact encoding is likely to require fewer memory reads and
writes.

True, there are some overheads with extra indexing and masking.
I would expect the relative cost of bit-per-byte or bit-per-bit
wold depend on the distribution of bitvector size and frequencey,
memory architecure, instruction set, etc etc.  But in general
if you're dealing with large bitvectors the compact encoding seems
like it should win.
--
	--Per Bothner
per@bothner.com   http://per.bothner.com/

_______________________________________________
Scheme-reports mailing list
Scheme-reports@scheme-reports.org
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports