A bug in my code
Denis Koroskin
2korden at gmail.com
Sat Sep 6 12:23:26 PDT 2008
On Sat, 06 Sep 2008 23:09:56 +0400, Denis Koroskin <2korden at gmail.com>
wrote:
> On Sat, 06 Sep 2008 05:12:56 +0400, bearophile
> <bearophileHUGS at lycos.com> wrote:
>
>> This code isn't short, but can someone help me spot the bug/problem
>> (D1, DMD)?
>> I have tried to write clean & short code, to help spotting problems.
>>
>> It produces an (no error line given):
>> Error: overlapping array copy
>>
>> It's just a stack data structure (here for simplicity just for items of
>> type int), made with a single linked list of blocks that become
>> geometrically bigger.
>>
>>
>> import std.gc: malloc, hasNoPointers;
>>
>> int min(int a, int b) {
>> return a <= b ? a : b;
>> }
>>
>>
>> class IntStack {
>> struct Block {
>> int len;
>> Block* next;
>> int* data;
>> }
>>
>> Block* list_head, list_tail;
>> int total_len;
>> int used_last_block; // how many items are used in the last (tail)
>> block
>>
>>
>> this() {
>> this.list_head = block_alloc(4);
>> this.list_tail = list_head;
>> }
>>
>>
>> ubyte* mem_alloc(int nbytes) {
>> auto p = cast(ubyte*)malloc(nbytes);
>> if (p is null)
>> throw new Error("not enough mem");
>> hasNoPointers(p);
>> return p;
>> }
>>
>>
>> Block* block_alloc(int nints) {
>> auto new_block = cast(Block*)mem_alloc(Block.sizeof);
>> new_block.data = cast(int*)mem_alloc(nints * int.sizeof);
>> new_block.len = nints;
>> new_block.next = null;
>> return new_block;
>> }
>>
>>
>> final void opCatAssign(int x) {
>> if (this.used_last_block == this.list_tail.len) {
>> // then last block is full and we must create a new one
>> this.used_last_block = 0;
>> auto new_block = block_alloc(this.list_tail.len * 2);
>>
>> // append to the linked list
>> this.list_tail.next = new_block;
>> this.list_tail = new_block;
>> }
>>
>> this.list_tail.data[this.used_last_block] = x;
>> this.used_last_block++;
>> this.total_len++;
>> }
>>
>>
>> int[] toarray() {
>> if (!this.total_len)
>> return null;
>>
>> int* result_ptr = cast(int*)mem_alloc(this.total_len *
>> int.sizeof);
>> int[] result = result_ptr[0 .. this.total_len];
>>
>> Block* aux_ptr = this.list_head;
>> int pos;
>>
>> // Here: Error: overlapping array copy
>> while (aux_ptr != null) {
>> // in the last block copy only up to the total_len
>> int ncopy = min(aux_ptr.len, this.total_len - pos);
>> result[pos .. pos + ncopy] = aux_ptr.data[0 .. ncopy];
>> pos += ncopy;
>> aux_ptr = aux_ptr.next;
>> }
>>
>> return result;
>> }
>> }
>>
>>
>> void main() {
>> auto st = new IntStack();
>>
>> for (int i; i < 70_000; i++)
>> st ~= i;
>>
>> auto aux = st.toarray;
>> aux = st.toarray;
>> }
>>
>>
>>
>> ---------------------
>>
>> Note: in that code I haven't used variable-length structs, like the
>> following idiom sometimes used in C, because it gives array bounds
>> errors:
>>
>>
>> struct Block {
>> int len;
>> Block* next;
>> int[1] data;
>> }
>> ...
>> auto new_block = cast(Block*)mem_alloc(Block.sizeof + (nints - 1) *
>> int.sizeof);
>>
>>
>> I presume that can't be done in D (I don't want to write code that
>> works only in release mode).
>>
>> Bye and thank you,
>> bearophile
>
> Just started digging your case. This behaviour is 100% repeatable with
> DMD1.028 but never takes place with DMD1.029+ (Windows).
WTF? Changing nearly *anything* (like, decreasing loop counf from 70_000
to 65_000, putting logging of any kind or commenting out almost any line)
makes problem disappear.
I think you should put the whole test program into bugzilla for Walter
play with. Even though it *looks like* problem is gone in 1.029+ it might
just be hidden and may arise under different circumstances.
More information about the Digitalmars-d-learn
mailing list