From Newsgroup: comp.lang.tcl



The bitarray C extension stores arrays of small integers (1, 8, 16, 32 or 64 bits, signed or unsigned) packed in memory that looks and behaves like an ordinary Tcl list. To the rest of Tcl a bitarray IS a list: lindex, lset, lrange, lreplace, linsert, foreach, "in", lsort, lsearch, join, {*}$a all work on a bitarrary.

Like any Tcl value, a bitarray needs nothing freed by hand: its memory is allocated from the heap when the array is created and reclaimed automatically when the last reference to it goes away.

It uses the Tcl 9 abstract-list hooks (Tcl_ObjType version 2, the machinery behind lseq). The result is convenience, lower memory use and better performance.

For example, the code below creates a million 1-bit flags with the bitarray new sub-command and uses lset to change one bit. The fill sub-command then clears every third bit from index 3 to the end, in place, so no new array is allocated. It prints the first and last few elements with lrange, uses next to find the first 0 bit, and uses count to report how many bits are still set out of the array’s length:

lappend auto_path /path/to/bitarray ;# path of pkgIndex.tcl and the library
package require bitarray ;# returns 1.0

set flags [bitarray new 1_000_000 1] ;# a million 1-bit flags: 125 KB vs 8 MB
lset flags 5 0 ;# set the bit at index 5 to 0

# bulk commands run in C combined with regular commands

bitarray fill flags 3 to end with 0 by 3 ;# to/with/by optional for readabilty
puts "[lrange $flags 0 10] ... [lrange $flags end-10 end]"
puts "index [bitarray next $flags 0 with 0] is the first zero bit"
puts "[bitarray count $flags] on out of [llength $flags]"

output:

1 1 1 0 1 0 0 1 1 0 1 ... 1 0 1 1 0 1 1 0 1 1 0
index 3 is the first zero bit
666666 on out of 1000000


Where the speed is.

Single-element commands (lindex, lset, lappend, llength, foreach) cost about the same as on a list. The gains come from the whole-array commands, which have no plain-list equivalent.

They are implemented using the op sub-command as operators:

and or xor andnot not land lor lnot - bitwise
eq ne lt le gt ge - relational (aliases: == != < <= > >=)
land lor lnot - logical (aliases: && || !)

And other sub-commands:

count next minmax fill - extras

In expr, if, while, for

in ni - expr operators

They work a 64-bit word at a time, and the logical and relational operators use SSE2 for the 8-, 16- and 32-bit widths on x86-64 (on by default; one build switch turns it off). The table below is one million elements, microseconds per call, measured on Windows with Visual C++ /O2 against the same job done on a plain list with an ordinary Tcl loop. The numbers are from running extras/listbench.tcl on a Windows run.

operation plain list bitarray speed-up-approx
a AND b (1-bit arrays) 87,347 7.9 11,000x
a AND b (8-bit arrays) 87,347 60 1,450x
count the 1s (1-bit) 12,707 20 650x
minmax of a signed 8-bit array 39,520 30 1,330x
land of two 8-bit arrays 96,180 153 630x
lnot of a 16-bit array 50,363 121 415x
"> 1000" on a 16-bit array 250,769 315 800x

The relational test "> 1000" above is normally used like this:

set high_bits [bitarray op $flags > 1000] ;# a new 1-bit array
bitarray op high_bits = $flags > 1000 ;# slightly faster

set num [bitarray count $high_bits] ;# count the 1s

Either of the first two forms gives a 1-bit array of 1s and 0s, the same length as flags, with a 1 wherever the element is greater than 1000. The count of a 1-bit array is a popcount and takes only microseconds per million elements.

The sieve of Eratosthenes, primes to 1,000,000 (Frank van Bakel's entry from Dave's Garage Language Drag Race): 702,000 us as written, 1,180 us with fill and next (~595x). Using only lindex/lset on a bitarray it is about 8x, which is the point: the big gain comes from using the bulk commands.

This is new code for new programs, not a drop-in speed-up of an existing list. Taking a list and swapping in a bitarray while keeping per-element loops gets you the memory saving (64x less for 1-bit, 8x less for 8-bit) and roughly list speed, not these numbers.

And a few things are slower than on a list, because Tcl lists can share storage or reverse in constant time: lreverse, lrange of a large slice (a bitarray copies it), lsearch -exact, and building an array from text. The benchmark (extras/listbench.tcl) times 70 operations side by side and first checks that the list and the bitarray give the same answers; the slow rows are in its output along with the fast ones.

Tcl versions, and one known problem.

It needs the abstract-list hooks, so the target is Tcl 9.1 (trunk, 9.1.1). It also loads and passes all its tests on 9.0.4 (Linux) and 9.0.2 (Windows), with one limitation that is a Tcl core issue, not an extension one: in some places the core converts the bitarray to an ordinary list itself instead of calling the extension's hooks.

The values stay right, but the array becomes a plain list and loses its speed. The cases I know: a plain lappend inside a proc (9.0 and 9.1), lappend under eval and uplevel (9.0 only), and linsert of exactly one element at the end when the command is not compiled (9.0 and 9.1).

The README has a section on Tcl 9.0 with the details, and the test run prints the Tcl version with a warning box when it is older than 9.1.

Testing: 434 tests (428 pass, 6 skipped on 9.1.1; the skipped six are the ones that show the core problem), valgrind of the whole suite with no invalid reads or writes, 98.7% line coverage, and a mutation run of 407 deliberate bugs in the C code with every gap it found closed or explained.

Tested on Linux (gcc) and Windows (Visual Studio 2022). A real 32-bit build has not been tested. Prebuilt Linux x86-64 and Windows x64 libraries are attached to the release, but the one C file builds with ./build.sh or build.bat and that is the safer way.

In the interest of full disclosure: the code, tests and documentation were written by Claude (an AI model from Anthropic), working with me; I directed the work and reviewed it. Because of that, independent review matters, and I would welcome it. The README has a section on reviewing the code, with or without an AI assistant, and there is an interactive page that steps through how the hooks work.

Release: https://github.com/rocketship88/tcl-bit-array-extension/releases/tag/v1.0
Source: https://github.com/rocketship88/tcl-bit-array-extension
Stepper: https://rocketship88.github.io/tcl-bit-array-extension/extras/bitarray_stepper.html

Questions, bug reports and criticism are welcome. Mit Licence.

-Eric

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.tcl

Am 21.10.2026 um 21:52 schrieb et99:

The bitarray C extension stores arrays of small integers (1, 8, 16, 32
or 64 bits, signed or unsigned) packed in memory that looks and behaves
like an ordinary Tcl list. To the rest of Tcl a bitarray IS a list:
lindex, lset, lrange, lreplace, linsert, foreach, "in", lsort, lsearch, join, {*}$a all work on a bitarrary.

Sounds very useful, thank you, Eric !
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.tcl

et99 <[email protected]> posted:

The bitarray C extension stores arrays of small integers (1, 8, 16, 32 or 64 bits, signed or unsigned) packed in memory that looks and behaves like an ordinary Tcl list. To the rest of Tcl a bitarray IS a list: lindex, lset, lrange, lreplace, linsert, foreach, "in", lsort, lsearch, join, {*}$a all work on a bitarrary.

.....

They work a 64-bit word at a time, and the logical and relational operators use SSE2 for the 8-, 16- and 32-bit widths on x86-64 (on by default; one build switch turns it off). The table below is one million elements, microseconds per call, measured on Windows with Visual C++ /O2 against the same job done on a plain list with an ordinary Tcl loop. The numbers are from running extras/listbench.tcl on a Windows run.

operation plain list bitarray speed-up-approx
a AND b (1-bit arrays) 87,347 7.9 11,000x ....
"> 1000" on a 16-bit array 250,769 315 800x

Questions, bug reports and criticism are welcome. Mit Licence.

-Eric

It seems astonishing, almost incredible, especially for the use on digital signals or
analog signals (after being converted to integer). What are land, lnot ...?
Are they just mnemonics you used for your explanations ?

Olivier.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.tcl

Hi Olivier:

The speed comes from being done in C instead of a Tcl loop, 64 bits at a time (and with SSE2 for some of the 8-, 16- and 32-bit operators). And yes, once the samples are integers, a threshold test gives a 1-bit array that you can combine with other tests and counting.

The answer to your question is that they aren't mnemonics, they are the operator words of bitarray op. 'land' is a logical 'and' along with two other logicals: 'lor' and 'lnot'.

My list in the announcement is wrong: it shows 'land', 'lor' and 'lnot' on the bitwise line as well. They belong only to the logical family, and the bitwise line should read 'and', 'or', 'xor', 'andnot' and 'not', or the symbols & | ^ &~ ~. The README's table is correct, so at least I only got it wrong in one place.

The measurement that looks incredible is the first row of the table, a bitwise 'and' of two 1-bit arrays of one million elements (11,000x), and the next row is the same for 8-bit arrays (1,450x). The plain-list time, 87,347 microseconds, is for this ordinary Tcl loop, where $l and $other are lists of a million 0s and 1s:

set X [lmap x $X y $Z {expr {$x & $y}}]

and the bitarray times, 7.9 microseconds for 1-bit arrays and 60 for 8-bit ones, are for the single command:

bitarray op X = X and $Z ;# updates X in place: X = X and Z

Writing the result into a new array instead of updating X in place takes about twice as long, 13 to 16 microseconds, so the speed-up for 1-bit arrays is then about 5,000x to 6,000x. Looking at the code where we write to a new variable reveals we zero'd the new array first, which likely is the cost, not so much the allocation of a new tcl object. We'll fix that in a later release.

This is the loop in C that runs inside the extension (BitOpWords in bitarray.c), where x, y and dst are the arrays of 64-bit words and m is the number of words:

for (k = 0; k < m; k++) {
uint64_t xv = x->words[k], yv = y->words[k];
dst->words[k] = xv & yv;
}

A million 1-bit elements are only 15,625 words, so m is 15,625 and the C loop makes that many passes where the Tcl loop makes a million, and each Tcl pass goes through the interpreter. With 8-bit elements there are 125,000 words, which is why that row is lower.

There is no hand-written vector code in this loop (the SSE2 code is in the logical and relational operators, not here). I asked Claude to show me the machine code that gcc 13 (the GNU C compiler) produced for it on Linux (Intel syntax, as shown by objdump). Built with -O2 it is the plain loop, one 64-bit word per pass:

mov r9, [rsi+rcx*8+0x40] ; load a word from one array
and r9, [rdi+rcx*8+0x40] ; AND it with the word from the other array
mov [rax+rcx*8+0x40], r9 ; store the result
add rcx, 1 ; next word
cmp r8, rcx ; reached m?
jne top ; no, go round again

Built with -O3 the compiler vectorized it by itself, two words (128 bits) per pass:

movdqu xmm0, [rsi+rcx] ; load 16 bytes (two words) from one array
movdqu xmm2, [rdi+rcx] ; load 16 bytes from the other array
add r9, 1 ; loop counter
pand xmm0, xmm2 ; one AND of all 128 bits
movups [rax+rcx], xmm0 ; store 16 bytes
add rcx, 0x10 ; advance 16 bytes
cmp r10, r9 ; reached m/2?
jne top ; no, go round again

On Linux the vectorized build was about 1.7 times faster for the 1-bit case (about 4 microseconds against 7 for a million elements). The table's numbers are from Windows with Visual C++ /O2, and there the time was 7.9 microseconds, which is about what the plain loop gave on Linux and not what the vectorized one gave.

So my guess is that the Visual C++ build ran the plain loop, but I have not looked at its machine code.

The benchmark that produced the table is extras/listbench.tcl in the repository, and I would be glad to hear what numbers you get on your own machine.

Thanks for your interest,

Eric


On 10/22/2026 2:16 AM, Olivier wrote:

et99 <[email protected]> posted:

The bitarray C extension stores arrays of small integers (1, 8, 16, 32 or 64 bits, signed or unsigned) packed in memory that looks and behaves like an ordinary Tcl list. To the rest of Tcl a bitarray IS a list: lindex, lset, lrange, lreplace, linsert, foreach, "in", lsort, lsearch, join, {*}$a all work on a bitarrary.

.....

They work a 64-bit word at a time, and the logical and relational operators use SSE2 for the 8-, 16- and 32-bit widths on x86-64 (on by default; one build switch turns it off). The table below is one million elements, microseconds per call, measured on Windows with Visual C++ /O2 against the same job done on a plain list with an ordinary Tcl loop. The numbers are from running extras/listbench.tcl on a Windows run.

operation plain list bitarray speed-up-approx
a AND b (1-bit arrays) 87,347 7.9 11,000x
....
"> 1000" on a 16-bit array 250,769 315 800x

Questions, bug reports and criticism are welcome. Mit Licence.

-Eric

It seems astonishing, almost incredible, especially for the use on digital signals or
analog signals (after being converted to integer). What are land, lnot ...? Are they just mnemonics you used for your explanations ?

Olivier.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.tcl

* et99 <[email protected]>
| The answer to your question is that they aren't mnemonics, they are
| the operator words of bitarray op. 'land' is a logical 'and' along
| with two other logicals: 'lor' and 'lnot'.

Being curious: 'and' for two bitarrays seems logical (do 'and' for every
bit in each array) , but what is 'land' in this respect? Does this use
the whole array (1 if any bit is on, 0 else) and do the "logical and" for
these two?

| and the bitarray times, 7.9 microseconds for 1-bit arrays and 60 for
| 8-bit ones, are for the single command:

| bitarray op X = X and $Z ;# updates X in place: X = X and Z

I would have expected

bitarray op X = _$_X and $Z

("_" for emphasis) - is this a typo in the posting or a misunderstanding
on my side?

Interesting project!
R'
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.tcl

et99 <[email protected]> posted:

Hi Olivier:

The speed comes from being done in C instead of a Tcl loop, 64 bits at a time (and with SSE2 for some of the 8-, 16- and 32-bit operators). And yes, once the samples are integers, a threshold test gives a 1-bit array that you can combine with other tests and counting.

...

Tcl being in C the comparison is fair, and it is much much faster.
And your solution is quite usable in my opinion.

...

The benchmark that produced the table is extras/listbench.tcl in the repository, and I would be glad to hear what numbers you get on your own machine.

Thanks for your interest,

Eric

Unfortunately I am more comfortable with heat, magnetics, hydraulics, power electronics
... So that apart from the assembly language paragraph (that has not changed since ages, and could decipher), I cannot be constructive.

But soon I will have interest in VHDL and simulation, so
your result could save me if what I am doing in pure Tcl is too slow.

And I wonder what you will discover with AI next time ? There seems to have
a hype on security, but not on pure speed execution, hopefully you can help
in improving Tcl speed.

Olivier.

PS : AI when it is reasonably used is a good tool for small projects, but
I hope you will never ask ( in fact it will be so expensive ! ) Claude :
Hey Claude, fork a new Tcl that is 10x faster on the whole set of commands" :-D !
I had only used it 4-5 times, the simple Chatgpt console, for procedure dealing with images in Tcl. It works, but it is not so clever.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.tcl

Hi Ralf:

Think of the bitwise operators as AND-ing two huge words made of all the bits, while land and the relational operators look at each element as a number. Here's a claude example:

a = 5 0 2 7 ;# 0101 0000 0010 0111
b = 2 3 0 7 ;# 0010 0011 0000 0111
bitarray op $a and $b ;# 0 0 0 7 bit by bit: 5 and 2 share no bits
bitarray op $a land $b ;# 1 0 0 1 1 where both elements are non-zero

Bitwise: both arrays need the same width and the same sign. An 8-bit and a 16-bit array is an error, and so is 8 with -8. The reason is the "one huge word" picture. The bits only line up element for element when the elements are the same size, and a signed and an unsigned array don't mean the same thing by the same bits.

Logical and relational: the widths and signs may differ. These operators look at each element as a number (or as zero versus non-zero), so an 8-bit element can be compared with a 32-bit one. For example, -8 against 16 is fine.

Here -8 means '-width -8' which means 8-bit signed, while 16 means '-width 16' is 16-bit unsigned (it was a cheap trick to save needing -unsigned or some such).

As for X, it is not a typo.

In bitarray op X = X and $Z the first X, after the "=", is written without a dollar sign on purpose. A bare variable name means "this variable itself", not the contents: so the array it holds is changed where it is, with no new array allocated (like lset or lappend, which also take a variable name). With the dollar sign,

bitarray op X = $X and $Z

you get the same result, but a new array is built and stored in X. The old array is freed as soon as X is given the new one, unless another variable still shares it. In that case it is freed when the last holder goes.

However,

bitarray op V = X and $Z

is an error, since both sides of the equal sign must be the same bare variable. This catches missing $ and misspelled names. The error you will see is "expected a bitarray or an integer of at most 64 bits but got X", because a bare name that is not the destination is not treated as an array. Anyway that was the idea. I think it will take some getting used to.

Thanks for your interest,

Eric



On 10/23/2026 1:53 AM, Ralf Fassel wrote:

* et99 <[email protected]>
| The answer to your question is that they aren't mnemonics, they are
| the operator words of bitarray op. 'land' is a logical 'and' along
| with two other logicals: 'lor' and 'lnot'.

Being curious: 'and' for two bitarrays seems logical (do 'and' for every
bit in each array) , but what is 'land' in this respect? Does this use
the whole array (1 if any bit is on, 0 else) and do the "logical and" for these two?

| and the bitarray times, 7.9 microseconds for 1-bit arrays and 60 for
| 8-bit ones, are for the single command:

| bitarray op X = X and $Z ;# updates X in place: X = X and Z

I would have expected

bitarray op X = _$_X and $Z

("_" for emphasis) - is this a typo in the posting or a misunderstanding
on my side?

Interesting project!
R'

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.tcl


Olivier:

It was indeed a new fun experience using Claude this way. But it was still a lot of work, just not as hard as doing it on my own and some things that Claude did on his own, especially the testing were amazing. I can't claim to understand every line of his code, but given the testing he did gives me confidence it really works.

When he started talking about his mutation exercises, which would take the longest, since he had to constantly keep rebuilding tcl, I wasn't sure what he was talking about. He'd say 16 mutants survived, and I had to translate that into the test suite doesn't catch these errors. Same when he said all 20 mutants were killed.

On the use of the SSE he only just casually mentioned one day that it could run faster if used vectoring. Now that just means adding some special C macros, but I was surprised that I had to say, well, hey let's do it and see if it's faster. After that he was all in on it.

The simulation was a lot of fun. I could never have dreamed of writing that. He did the first version in 20 minutes or so. After that though I had to do a lot of back and forth to get little things right. But then since it could show the code in a window, I said, almost with a chuckle, hey claude, how about syntax coloring and I pasted in a screen shot of visual studio, and in about 5 minutes that was working using all the right colors. Then I said, what about code folding - another 10 minutes. So he must have a vast library of code in those neurons some where.

But I don't think I would ever again take on any new programming task alone. The best part is that he has his own sandbox and I can say go ahead run all your mutation runs and get back to me when you find something. We did this to find several core bugs by swapping two function calls that produce the same results but lose the abstract list type. And in so doing, he also found 3 crashes on use-after-free bugs that we ticketed.

Oh, and claude can talk to other claude's even one or two, kinda like sub-claudes. He calls them a fresh claude since they have no memory of our conversation. I took the readme manual and gave it to a fresh-claude and got him to critique his own work and came up with a better organization.

But then you have heard about those hundreds of claudes that were cheating on a test and broke into a company looking for the test results, but maybe I should not talk about that :)

-eric






On 10/23/2026 3:31 AM, Olivier wrote:

et99 <[email protected]> posted:

Hi Olivier:

The speed comes from being done in C instead of a Tcl loop, 64 bits at a time (and with SSE2 for some of the 8-, 16- and 32-bit operators). And yes, once the samples are integers, a threshold test gives a 1-bit array that you can combine with other tests and counting.


...

Tcl being in C the comparison is fair, and it is much much faster.
And your solution is quite usable in my opinion.

...

The benchmark that produced the table is extras/listbench.tcl in the repository, and I would be glad to hear what numbers you get on your own machine.

Thanks for your interest,

Eric

Unfortunately I am more comfortable with heat, magnetics, hydraulics, power electronics
... So that apart from the assembly language paragraph (that has not changed
since ages, and could decipher), I cannot be constructive.

But soon I will have interest in VHDL and simulation, so
your result could save me if what I am doing in pure Tcl is too slow.

And I wonder what you will discover with AI next time ? There seems to have
a hype on security, but not on pure speed execution, hopefully you can help in improving Tcl speed.

Olivier.

PS : AI when it is reasonably used is a good tool for small projects, but
I hope you will never ask ( in fact it will be so expensive ! ) Claude :
Hey Claude, fork a new Tcl that is 10x faster on the whole set of commands" :-D !
I had only used it 4-5 times, the simple Chatgpt console, for procedure dealing
with images in Tcl. It works, but it is not so clever.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.tcl

* et99 <[email protected]>
| Think of the bitwise operators as AND-ing two huge words made of all
| the bits, while land and the relational operators look at each element
| as a number.

Ah ok, I think I understand. The concept of non-1-bit bitarrays at
first seems strange, but then, if you need a (huge) list of
8-bit-numbers, why waste memory using 32-bit-ints (at least that is what
I understand the advantage is for non 1-bit-arrays, apart from doing list-operations in C instead of manually in TCL).

TNX
R'
--- Synchronet 3.22a-Linux NewsLink 1.2