一个中国象棋程序，内存管理的问题。我要思路，无须代码。

liuhaixiao1980 · 发表于 2003-10-21 18:23:14

关于树的结点的生成和删除，树的结点有很多，可以说是1.0*10^8个这样类似的数据，每个结点又很小，只有几百Byte。
如果我只使用malloc()和free()用于结点的生成和删除，树的结点很多，由于malloc()和free()用到了系统调用，要占用不少的时间，更何况有时必未能申请成功，十分不便，大量的小内存块分散在整个系统内存里恐怕可靠性也不好。我计划程序开始时用malloc()一次性向系统申请一大块内存，用自已内存管理函数管理这一块内存，所有的结点的生成和删除都只在这一块内存里进行，程序结束后向系统归还这一大块内存。程序内部的内存申请和归还函数是malloc1()和free1()。
问题一：malloc()申请到的内存是不是连续的？如果不是，那我将用一维静态数组来申请内存，但是可以对静态数组的这块内存进行操作吗？
问题二：假设现在已经申请到了一块首地址为mHead,大小为mTotal Byte的连续内存。那关于malloc1()和free1()函数的问题是，我将用一个二维表记录已经申请使用的每个小内存块的起始地址和结束地址，但是由于每个结点都很小，只有200Byte,这一大块内存可以被申请很多小内存块用作结点，在不断地申请和释放内存的过程中会产生很多碎片，这个用作记录已经申请使用的每个小内存块二维数组岂不是很大？
考虑到速度，程序本身的内存管理函数malloc1()和free1()内部也是不能用malloc()和free()的，也就是说用作记录已经申请使用的每个小内存块二维表一定是个静态数组形式，不会是链表。
此外，也是考虑到速度问题，最好不要对这一大块的内存进行“内存碎片整理”的操作。
这用作记录已经申请使用的每个小内存块二维表要占很大内存，有没有减小内存管理函数使用内存大小的解决方案？
没有就算了。

sjinny · 发表于 2003-10-21 22:33:22

我经常看到别人为了性能而自己管理内存，但是我一直很疑惑，有必要吗？
首先，系统调用真的那么费时吗？
第二，自己管理内存，恐怕管理得不一定比系统管理得好
大家是否讨论一下内存使用方面的问题？

liuhaixiao1980 · 发表于 2003-10-21 23:25:07

老大！
我这个问题绝对是有必要的！！！！
树有很多结点，每个结点又很小，更重要的是经常要生成和删除结点，结点的创建和删除占去了大部分的工作，如果能省一点点时间，积累起来就很可观了。
我试了下，可以申请到3G多的内存，我机器是Redhat9.0,linux2.4.20,Ram256M,swap768M，hda60G+hdb80G。
我自已来管理内存，也就是几条C语句就可以搞定了，用系统的不知道系统要搞多久，要是从系统分配不到内存呢？释放已申请的内存？要是我释放了已申请某些内存，那系统会保证这释放的资源会马上可以给我的程序另一部分得到吗？
CSDN上的一位高手的指点：用结点数组。
今天身体不适，少写几句，请见谅。

sjinny · 发表于 2003-10-22 12:38:22

呵呵，我没学操作系统原理，不知道系统调用是怎么回事~~

其实，如果每个节点的大小都一样，那么可以把申请到的整块的内存当做一个大的数组，然后节点间的关系使用数组下标来联系。这样，删除一个节点其实只是不再使用某个节点所占的空间，而每个节点其实可以看做整块内存这个表格中的一小格。那么，使用情况是这样的：
整块内存中会有一段一段的空闲空间，这些空间可以看作是一个一个的小格（节点）组成的，那么对于某一段空闲空间，只需要记录两样信息：这个空间里第一个节点在整块数组中的数组下标，从这个节点开始向后数（包括这个节点）共有多少个空闲节点空间。不过还有个问题，如果使用数组来记录空间使用情况，那么要够用的话就得有 n/2 个数组元素（假设整块内存中有n个节点的空间），这样在最坏的情况下，也就是使用的和没用的相间隔地分布在整块内存中的情况下，也够用。但是这样这个数组还是太大了啊。而且，恐怕大多数时候都有很多数组元素没用上。要是用链表，恐怕性能上就不行了。不知道有什么更好的办法~~

liuhaixiao1980 · 发表于 2003-10-22 21:42:52

我打算用结点数组。
结点是很多的，内存和CPU是永远不够用的，我只能生成其中一部分和搜索其中一部分。

sjinny · 发表于 2003-10-22 22:37:16

晕，看不懂哦，具体说说？

liuhaixiao1980 · 发表于 2003-10-23 07:42:25

估算：一步约有40种变化，要达到一定水平，至少能算10个回合的变化，10回合就是20步棋，21步棋将会有40^20=1.1*10^32种变化。我的赛扬CPU频率只有1.7G=1.7*10^9，一个CPU时钟周期就是
1/1.7G=5.9*10^-10s
假设一个CPU时钟周期内能算一种变化(实际上是算一种变化要执行上百条机器指令，执行一条机器指令要若干个CPU时钟周期，),算完1.1*10^32种变化要用
1.1*10^32*5.9*10^-10s=6.5*10^22s=1.07*10^21m=1.8*10^19h=7.4*10^17d=2.0*10^15y。
由此可见，我们不能用简单的、死板的算法，这样是不可能实观的。

估算：如果平均每步用时1分钟，1.7G，共有1.7G*1*60=1.02*10^11个CPU时钟周期，

估算：5个回合有：40^10=1.048576*10^16种变化，不算根结点，棋树有40+40^2+40^3+。。。+40^9=(40-40^11)/(1-40)=1.075426*10^16个结点

估算：3个回合有：40^6=4.096*10^9种变化。棋树有(40^7-40)/(40-1)=4.2*10^9个结点。

liuhaixiao1980 · 发表于 2003-10-23 07:45:58

Now I am in the FVWM , the setup is no good , I can't use Chinese input .
the beyond note was pasted from my notebook.

		自动登录	找回密码
密码			注册