php 로 IntegerArray 구현하기

11/27/2019

기본적으로 PHP 의 배열은 일반적인 ArrayList 구현이 아니라, Hash Table 입니다.
그러다보니 php 개발자들은 배열을 배열처럼 쓰지 않고 Hash Table 처럼 이용하는 분들이 많습니다.
(나쁜거 아니에요!)

php
1$a = ['q_lazzarus' => '킹왕짱'];
2echo $a['q_lazzarus'];

다시 기초로 돌아가자면, array 는 동일한 자료구조의 반복 입니다.

메모리 단위에서 생각해보면 동일한 크기의 방이 주루룩 있는 구조이죠.

그렇다면, string 하나에 integer 몰빵해서 넣으면 되자너?

구현해보자 !

5개의 원소가 있는 배열이 있다고 가정하고 데이터를 읽는 간단한 함수를 만들어 보겠습니다.

php
1function array_get($i) {
2    $data = '12345';
3    return substr($data, $i, 1);
4}
5
6echo array_get(3);

짜잔! 이렇게 string 변수를 참조하여, 값을 리턴하는 간단한 코드가 만들어졌습니다.
하지만 당연하게도 이건 못 씁니다.
왜냐하면 원소의 데이터가 0~9 까지만 허용하는 말도 안되는 구현이기 때문입니다.

자료형 ??

가만히 다시 생각해 봅시다. 설마 integer 데이터를 메모리에 string 처럼 저장하지 않겠죠...
보통의 경우 integer 자료형은 4 Bytes 를 차지하고 있습니다.

Data Type	Size (in bytes)	Range
short int	2	-32,768 to 32,767
unsigned short int	2	0 to 65,535
unsigned int	4	0 to 4,294,967,295
int	4	-2,147,483,648 to 2,147,483,647
long int	4	-2,147,483,648 to 2,147,483,647
unsigned long int	4	0 to 4,294,967,295
long long int	8	-(2^63) to (2^63)-1
unsigned long long int	8	0 to 18,446,744,073,709,551,615
singed char	1	-128 to 127
unsigned char	1	0 to 255

호오 그렇다면? 데이터를 변환해서 넣도록 하겠습니다.
다행히 php 에서는 pack 이라는 함수가 이러한 변환을 편하게 도와줍니다.

php
1$data = str_repeat(pack('I', null), 5);
2
3function array_get($i) {
4    global $data;
5    $binary = substr($data, $i * 4, 4);
6    $unpack = unpack('I', $binary);
7    return $unpack[1];
8}
9
10function array_set($i, $value) {
11    global $data;
12    $binary = pack('I', $value);
13    $data = substr_replace($data, $binary, $i * 4, 4);
14}
15
16array_set(3, 65535);
17echo array_get(3);

오 이번에는 10 을 넘어서 심지어 65535 도 잘 나오고 있습니다.
하지만 아직 문제가 있습니다.

php
1echo array_get(2);

아니 어떻게 된 일이죠?? 분명히 공간만 만들어주기 위해서 null 을 넣어주었는데?

사실은 integer 자료형에서는 null 은 없습니다.
왜냐하면 null 은 null 이기 때문입니다. (자료형도 달라요)
그렇다보니 저희가 만든 함수에서는 null 은 처리가 불가능 합니다.
그럼 어떻게 해야할까요?

꼼수 ??

생각해보면 데이터를 넣을때 한칸씩 미루면 되지 않을까요?

php
1$data = str_repeat(pack('I', 0), 5);
2
3function array_get($i) {
4    global $data;
5    $binary = substr($data, $i * 4, 4);
6    $unpack = unpack('I', $binary);
7    $result = $unpack[1];
8    if (0 === $result) {
9        return null;
10    }
11    return $result - 1;
12}
13
14function array_set($i, $value) {
15    global $data;
16    if (null !== $value) {
17        $value = $value + 1;
18    }
19    $binary = pack('I', $value);
20    $data = substr_replace($data, $binary, $i * 4, 4);
21}
22
23var_dump(array_get(3));


1NULL

이렇게 되면 데이터 제한이 4,294,967,295 에서 하나 소모가 되지만,
이 정도면 괜찮은 것 같습니다.

실제 배열처럼 바꿔 보아요

어느정도 된 것 같습니다. 하지만 이것을 실제 배열 처럼 쓰기에는 아직 부족합니다.
그래서 php 에서는 Array 구현하기 위한 interface 를 제공합니다.

php
1ArrayAccess {
2    /* Methods */
3    abstract public offsetExists ( mixed $offset ) : bool
4    abstract public offsetGet ( mixed $offset ) : mixed
5    abstract public offsetSet ( mixed $offset , mixed $value ) : void
6    abstract public offsetUnset ( mixed $offset ) : void
7}

클래스를 마치 php 기본 배열 처럼 접근 가능하게 하는 구현체이며
제한적인 의미로 accessor overloading 입니다.

php
1$obj = new obj;
2$obj[] = 'hello';
3$obj[] = 'world';
4
5echo $obj[0] . ' ' . $obj[1];


1hello world

실제 구현은?

php
1class FixedUnsignedIntegerArray implements Iterator, ArrayAccess, Countable
2{
3    const BINARY_FORMAT = 'I';
4    private $position = 0;
5    private $length = 0;
6    private $binaryLength = 0;
7    private $data = null;
8    public function __construct($length)
9
10    {
11        $null = $this->convertBinary(null);
12        $this->position = 0;
13        $this->length = $length;
14        // because binary length is machine dependency
15        $this->binaryLength = strlen($null);
16        $this->data = str_repeat($null, $length);
17    }
18
19    private function getEntry($position)
20    {
21        $position = $position * $this->binaryLength;
22        $unpack = unpack(self::BINARY_FORMAT, substr($this->data, $position, $this->binaryLength));
23        $result = false !== $unpack ? $unpack[1] : null;
24        if (0 === $result) {
25            return null;
26        } else {
27            return $result - 1;
28        }
29    }
30
31    private function setEntry($position, $value)
32    {
33        $position = $position * $this->binaryLength;
34        $this->data = substr_replace($this->data, $this->convertBinary($value), $position, $this->binaryLength);
35    }
36
37    private function convertBinary($value)
38    {
39        if (null !== $value) {
40            $value = $value + 1;
41        }
42        return pack(self::BINARY_FORMAT, $value);
43    }
44
45    public function rewind()
46    {
47        $this->position = 0;
48    }
49
50    public function current()
51    {
52        return $this->getEntry($this->position);
53    }
54
55    public function key()
56    {
57        return $this->position;
58    }
59
60    public function next()
61    {
62        $this->position = $this->position + 1;
63    }
64
65    public function valid()
66    {
67        return $this->offsetExists($this->position);
68    }
69
70    public function offsetSet($offset, $value)
71    {
72        if (is_integer($offset) && $offset < $this->length && $offset >= 0) {
73            $this->setEntry($offset, $value);
74        } else {
75            throw new InvalidArgumentException('overflow array offset');
76        }
77    }
78
79    public function offsetExists($offset)
80    {
81        return ($offset < $this->length && $offset >= 0);
82    }
83
84    public function offsetUnset($offset)
85    {
86        $this->setEntry($offset, null);
87    }
88
89    public function offsetGet($offset)
90    {
91        return $this->getEntry($offset);
92    }
93
94    public function count()
95    {
96        return $this->length;
97    }
98}

pack 함수의 설명을 다시 보자면, 환경에 따라 다른 byte 수가 나올 수 있습니다.

unsigned integer (machine dependent size and byte order)

따라서 integer byte 수를 저희가 알고 있어야 잘못된 주소를 참조하지 않도록 하겠습니다.
실제 구현에서는 Iterator, ArrayAccess, Countable 을 구현하여 좀 더 효용성을 높였습니다.

성능 테스트!

이제 구현했으니, 성능을 테스트 해보겠습니다.

테스트는 다음과 같이 진행하였습니다.

10000 크기의 고정 배열을 만들어서 랜덤으로 데이터를 넣었을때 메모리 사용량을 체크 하였습니다.
100번씩 반복문을 실행하여, 실행 시간의 평균을 체크 하였습니다.

php
1define('ARRAY_LENGTH', 10000);
2
3$start_memory = memory_get_usage();
4$vanilla = [];
5for ($i = 0; $i < ARRAY_LENGTH; $i++) {
6    $vanilla[] = mt_rand(0, 255);
7}
8
9$end_memory = memory_get_usage() - $start_memory;
10echo "legacy array memory usage : {$end_memory}\n";
11
12$start = microtime(true);
13$result = 0;
14for ($i = 0; $i < ARRAY_LENGTH; $i++) {
15    $result += $vanilla[$i];
16}
17
18$time_elapsed_secs = microtime(true) - $start;
19echo "for iterator legacy array : {$time_elapsed_secs}\n";
20
21$start_memory = memory_get_usage();
22$entries = new \Monoless\Arrays\FixedUnsignedIntegerArray(ARRAY_LENGTH);
23for ($i = 0; $i < ARRAY_LENGTH; $i++) {
24    $entries[$i] = mt_rand(0, 255);
25}
26
27$end_memory = memory_get_usage() - $start_memory;
28echo "fixed unsigned integer array memory usage : {$end_memory}\n";
29
30$time_total = 0;
31$interval = 100;
32for ($j = 0; $j < $interval; $j++) {
33    $start = microtime(true);
34
35    $result = 0;
36    for ($i = 0; $i < ARRAY_LENGTH; $i++) {
37        $result += $entries[$i];
38    }
39
40    $time_elapsed_secs = microtime(true) - $start;
41    $time_total += $time_elapsed_secs;
42}
43
44$time_average = $time_total / $interval;
45echo "iterator speed average : {$time_average}\n";


1legacy array memory usage : 528440
2for iterator legacy array : 0.00035810470581055
3fixed unsigned integer array memory usage : 41072
4iterator speed average : 0.0068418407440186

메모리 사용량은 약 90% 개선이 되었으나 속도는 기존 배열을 이길 수가 없었네요...

역시 기존껄 쓰는거 좋은거라고 배우고... 오늘도 맥주와 치킨을 시키며 잡니다.
그래도 제 삽질이 좋다면, github 와 이 패키지를 참고하세요

후일담...

혹시나 싶어서 php://memory 에 fwrite / fseek 를 구현해봤는데 더 느렸습니다...


1for iterator legacy array : 0.0013089179992676
2string speed average : 0.0084279131889343
3php://memory speed average : 0.0098107981681824

참조 사이트

Relate
Stories

babel 이란 무엇인가?

coding

5 years ago

최근에 react 프로젝트와 typescript 프로젝트를 거치면서 webpack 을 자주 써보고 세팅해보게 되었습니다. 처음에는 동작의 원리보다 `요즘 잘나가는 프론트엔드 개발 환경 만들기`라는 목표로 세팅 하였으나 점점 처음부터 차근 차근 만지면서, 내가 이걸 몰랐구나 이게 이런 뜻이었구나 새삼 느끼게 되었습니다.

dev coding javascript webpack babel polyfill esnext typescript