2007-01-07

从简单测试看D数组内存分配策略

关键字: 数组分配策略
D语言动态数组可以在运行期改变大小，这和C++的vector相似。似乎记得“STL源码分析”一书中提到vector的内存分配策略是倍增方式的，D语言数组是不是也使用了相同方式呢？我做了个简单的测试： 

void main(){
        void* ptr = null;
        int[] arr = new int[0];
        for (int i=0; i<33; ++i){
                void* cur = cast(void*)arr;
                if (cur != ptr){
                        writefln(i);
                        ptr = cur;
                }
                arr ~= 0;
        }

        writefln("=================");

        while (arr.length){
                void* cur = cast(void*)arr;
                if (cur != ptr){
                        writefln(arr.length);
                        ptr = cur;
                }
                arr.length = arr.length - 1;
        }
}

上面的代码先是在数组中加入元素，如果数组地址发生变化，则表明内在已经重新分配了。然后是删除元素，改变数组的长度就可以做到。

运行结果如下： 
1
4
8
16
32
=================

基本可以确定它是使用了倍增的分配策略，而删除元素时并不重新分配空间（这也是预期的）。

我们知道这种分配策略是会拷贝数组元素的，如果要减少这种拷贝，就需要在创建数组时分配足够的空间。如何分配一个可以容纳1024个元素的空间，但它的长度却为0？

由于D的文档经常悄悄地添加一些东西，所以我重新看了一下D语言文档数组部分，以防有新的做法是我没有看到的，不过并没有找到这种直接的做法（如果你的到了请告诉我，谢谢）。

根据上面的测试代码，最合理的一种做法大概是： 
int[] arr = new int[1024];
arr.length = 0;

然后进行数组元素的添加操作，不会引起内在的重新分配。
评论
发表评论

您还没有登录，请登录后发表评论

qiezi
搜索本博客
存档
最新评论