Calculation of small memory specifications in php (code example)

The content of this article is about the calculation of small memory specifications in PHP (code examples). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

small memory allocation calculation bin_num

In the PHP source code, there is a calculation of small memory specifications, specifically in the zend_mm_small_size_to_bin function of Zend/zend_alloc.c, its purpose is to pass in a size , calculate the corresponding specifications. See the code:

if (size <= 64) {
    /* we need to support size == 0 ... */
    return (size - !!size) >> 3;
} else {
    t1 = size - 1;
    t2 = zend_mm_small_size_to_bit(t1) - 3;
    t1 = t1 >> t2;
    t2 = t2 - 3;
    t2 = t2 << 2;
    return (int)(t1 + t2);
}

It can be seen that this code is divided into two situations for discussion:

• 1. The case where size is less than or equal to 64;

• 2. The case where size is greater than 64;

Let’s analyze these two situations in detail below.

For the case where size is less than or equal to 64

• SeeZEND_MM_BINS_INFOThis macro knows that when size is less than or equal to 64, it is an arithmetic sequence, increasing 8, so just use size divided by 8 (right shift by 3 bits in the source code) size >> 3</pre> <li><p>But you must consider that size is equal to 8, 16 and so on, so <code>(size - 1) >> 3

• Then we need to consider the situation of 0, so ## in the source code The processing of #-1 is !!size. When size is 0, !!0 = 0. So when size is 0, -1 is converted into -0, and finally there is the expression (size - !!size) >> in the source code ; 3

For the case where size is greater than 64

t1 = size - 1;
t2 = zend_mm_small_size_to_bit(t1) - 3;
t1 = t1 >> t2;
t2 = t2 - 3;
t2 = t2 << 2;
return (int)(t1 + t2);

Initial confusion
• When I first saw this code, It’s easy to get confused, what are these t1 and t2?

• But don’t be afraid, let’s analyze it step by step

##Step analysis

/* num, size, count, pages */
#define ZEND_MM_BINS_INFO(_, x, y) \
    _( 0,    8,  512, 1, x, y) \
    _( 1,   16,  256, 1, x, y) \
    _( 2,   24,  170, 1, x, y) \
    _( 3,   32,  128, 1, x, y) \
    _( 4,   40,  102, 1, x, y) \
    _( 5,   48,   85, 1, x, y) \
    _( 6,   56,   73, 1, x, y) \
    _( 7,   64,   64, 1, x, y) \
   
    _( 8,   80,   51, 1, x, y) \
    _( 9,   96,   42, 1, x, y) \
    _(10,  112,   36, 1, x, y) \    
    _(11,  128,   32, 1, x, y) \
    
    _(12,  160,   25, 1, x, y) \    
    _(13,  192,   21, 1, x, y) \
    _(14,  224,   18, 1, x, y) \    
    _(15,  256,   16, 1, x, y) \
    
    _(16,  320,   64, 5, x, y) \    
    _(17,  384,   32, 3, x, y) \
    _(18,  448,    9, 1, x, y) \    
    _(19,  512,    8, 1, x, y) \
    
    _(20,  640,   32, 5, x, y) \
    _(21,  768,   16, 3, x, y) \
    _(22,  896,    9, 2, x, y) \    
    _(23, 1024,    8, 2, x, y) \
    
    _(24, 1280,   16, 5, x, y) \
    _(25, 1536,    8, 3, x, y) \
    _(26, 1792,   16, 7, x, y) \    
    _(27, 2048,    8, 4, x, y) \
    
    _(28, 2560,    8, 5, x, y) \
    _(29, 3072,    4, 3, x, y)

#endif /* ZEND_ALLOC_SIZES_H */

• size = size - 1;

  This is a boundary case, just like the previous one, the sizes that appear later are considered to be nearly reduced by one

Assuming we don’t look at this source code, we need to find the corresponding bin_num in
• ZEND_MM_BINS_INFO
  ## is learned from
ZEND_MM_BINS_INFO
• Subsequently, 4 will be added as a group, respectively

  2^4, 2^5, 2^6...

With this grouping information, we need to find the bin_num corresponding to siez

Find which group this size belongs to

• And what is the offset of the size within the group

• Calculate the starting position of the group
Now the problem is converted into the above three small problems, let’s solve them one by one

• The easiest way to find which group the size belongs to is to compare the sizes, right? You can use if...else to compare one by one, but obviously the PHP source code does not work like this, then What other options do we have?
We can’t see anything interesting in decimal, so let’s convert these values ​​into binary and have a look

• 64  | 100 0000
  80  | 101 0000
  96  | 110 0000
  112 | 111 0000
  
  128 | 1000 0000
  160 | 1010 0000
  192 | 1100 0000
  224 | 1110 0000
  
  256 | 1 0000 0000
  320 | 1 0100 0000
  384 | 1 1000 0000
  448 | 1 1100 0000
  
  .....

• If we look at the binary numbers above, we will find that the lengths of the binary numbers in each group are equal, and each of the following ones has one more digit than the previous one.

That means we can calculate the length of the binary number. Determine its grouping, then what is the length of the binary? In fact, it is the number of digits where the highest bit of the current binary is
1
• Then the question is converted to Find the number of digits of the highest bit

  1 in the binary number

• The solution to the PHP source code is given below. We will not parse it here for the time being, as long as you know that it returns the binary number The number of digits of the highest

  1

int n = 16;
if (size <= 0x00ff) {n -= 8; size = size << 8;}
if (size <= 0x0fff) {n -= 4; size = size << 4;}
if (size <= 0x3fff) {n -= 2; size = size << 2;}
if (size <= 0x7fff) {n -= 1;}
return n;

• Assuming that the size we apply for is 65, then n here returns 7

Calculate the offset of size within the group

• This is simple, directly subtract the starting siez size of each group from size and then divide it by the current group The difference (16, 32, 64...) is enough, that is,
(size-64)/16 (size-128)/32 (size-256)/64
• Now let’s take a look at the returned value in the previous step. Each group is

  7, 8, 9..., so let’s now take a look at how to calculate such data. The offset within the group

(size - 2^4 * 4) / 16 = size / 2^4 - 4

(size - 2^5 * 4) / 32 = size / 2^5 - 4   

(size - 2^6 * 4) / 64 = szie / 2^6 - 4

• Can we use 7, 8, 9

  minus
3
Get
4, 5, 6
• , so that we can get the difference of the current group (16, 32, 64...) based on the information of which group it is in

  When size is 65, is the offset equal to

  (64-64) / 2^4 = 0

  Calculate the starting position of the group

• Now we have Offset information, assuming our grouping is 1, 2, 3
, does that mean subtracting
from the number of digits in the highest bit
• 1

  ? 6

  You can get the grouping information

• After getting the grouping information, how do you know the starting position of each group

  We know The starting positions are
8, 12, 16...
• It is also an arithmetic sequence, which is

  4n 4

• We are looking at Look at the example of size=65

• 计算的偏移量是0

• 计算的起始位置是4*1 + 4 = 8

• 所以当size=65的bin_num就是起始位置加上偏移量 8 + 0 = 8

• 我们再看一个size=129的例子

• 二进制中最高位的1的位数为8

• 然后用8减去3得到5

• (129 - 1 - 32 * 4) / 64 = 0

• 偏移量是

• 计算起始位置是 4 * 2 + 4 = 12

• 两者相加就是 12 + 0 = 0

• size=193

• 二进制中最高位的1的位数为8

• (193 - 1 - 32 * 4) / 64 = 2

• 偏移量是

• 计算起始位置是 4 * 2 + 4 = 12

• 两者相加就是 12 + 2 = 14

• size=1793

• 二进制中最高位的1的位数为11

• (1793 - 1 - 256 * 4) / 256 = 3

• 偏移量是

• 计算起始位置是 4 * 5 + 4 = 24

• 两者相加就是 24 + 3 = 27

代码分析

php实现代码

1 t1 = size - 1;
2 t2 = zend_mm_small_size_to_bit(t1) - 3;
3 t1 = t1 >> t2;
4 t2 = t2 - 3;
5 t2 = t2 << 2;
6 return (int)(t1 + t2);

第一行

• t1 = size - 1;

• 是为了考虑size为64、128...这些边界情况

第二行

• t2 = zend_mm_small_size_to_bit(t1) - 3;

• 这里调用了zend_mm_small_size_to_bit这个函数，我们看看这个函数

/* higher set bit number (0->N/A, 1->1, 2->2, 4->3, 8->4, 127->7, 128->8 etc) */

int n = 16;
if (size <= 0x00ff) {n -= 8; size = size << 8;}
if (size <= 0x0fff) {n -= 4; size = size << 4;}
if (size <= 0x3fff) {n -= 2; size = size << 2;}
if (size <= 0x7fff) {n -= 1;}
return n;

• 看注释我们就知道这个函数是用来返回当前size二进制中最高位1的位数，具体的做法呢其实就是二分法

• 我们通过zend_mm_small_size_to_bit这个函数获取了size二进制中最高位1的位数，那么这个 -3 是什么神奇的操作呢

  (size - 2^4 * 4) / 16 = size / 2^4 - 4  
  
  (size - 2^5 * 4) / 32 = size / 2^5 - 4 
  
  (size - 2^6 * 4) / 64 = szie / 2^6 - 4

• 这里获取二进制的位数是7、8、9...通过 -3 的操作来获取相应的 4、5、6...

• 上问的分析中提到，我们计算size在组内的偏移量的公式

第三行

• t1 = t1 >> t2;</pre></h3> <li><p>把t1右移t2位，这又是什么神奇的操作？</p></li> <li><p>这里我们把最后计算bin_num的数学公式给写出来，它是等于每组的起始位置加上组内的偏移量</p></li> <div class="code" style="position:relative; padding:0px; margin:0px;"><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">binnum = (4n + 4) + (size / 2^n - 4) binnum = 4n + size / 2^n</pre><div class="contentsignin">Copy after login</div></div><div class="contentsignin">Copy after login</div></div> <ul class=" list-paddingleft-2"><li><p>所以第三行的意思我们就知道了，就是size右移2^n次方为</p></li></ul> <h4 id="第四行">第四行</h4> <ul class=" list-paddingleft-2"> <li><p><code>t2 = t2 - 3;

• 这个好理解，可以参照上文得到每组的起始位置的方法

第五行

• t2 = t2 << 2;

• 我们再看看bin_num的计算公式

binnum = (4n + 4) + (size / 2^n - 4)

binnum = 4n + size / 2^n

• 那么这行就好理解了，就是计算每组的起始位置4n对吧，左移两位就是乘以4

第六行

• return (int)(t1 + t2);

• 这行没啥说的，就是返回了一个int类型的bin_num

The above is the detailed content of Calculation of small memory specifications in php (code example). For more information, please follow other related articles on the PHP Chinese website!