[PYTHON] Stack processing speed comparison by language

1.First of all

Stack is not implemented in Go language,

The Stack process itself is in any language You can implement it yourself using arrays and linear lists.

In addition to making my own for Go language I compared the processing speed (processing time) with other languages in which Stack is implemented.

The language used in the experiment was

There are 5 languages.

The source of each language is also published on github. https://github.com/NobuyukiInoue/StackSpeedTest

2. Method comparison by language

Even though it is called Stack, various operations are provided by methods depending on the language, The implementation contents of detailed processing are different, such as having to check in the property.

The following is a list of classes / interfaces / functions in each language used in this experiment.

Processing content C#(.NET Core3.x)
(Stack class)
Java 8
(Class Stack)
Java 8
(Class ArrayDeque)
Java 8
(Class Deque)
Write to Stack Push method push method push method addFirst method append function
Eject from Stack Pop method pop method pop method removeFirst method pop function
Search for value Contains method
(Return value is bool type)
search method
(The return value is the index number)
Contains method
(Return value is bool type)
Contains method
(Return value is bool type)
index function
Check if Stack is empty Use Count property empty method isEmpty method isEmpty method Use len function

3. Verification environment and experimental results (added on 2020/07/11)

item value
OS MS-Windows 10
CPU Intel Core-i7 8559u
memory 16GB(LPDDR3/2133MHz)

Added memory capacity. (2020/07/11)

The content of the process is


(The reason for 100 million is that the processing time between each language started to open from around here. Unless you implement the huge JSON parse processing on the stack, it will not consume that much.)

If you allocate 100 million numbers with int64 (8byte), you will need a capacity of 762MByte. If it is int32 (4byte), it is half 381MByte.

As long as the capacity of the generated stack is small, there is not much difference in processing time, When it comes to generating 100 million stacks, memory consumption can exceed 4GB, depending on the method you choose.

If the installed memory is 8GB or less, depending on the language (by default setting), I get an error saying that the heap memory is insufficient.

The processing time in each language was as follows.

The memory consumed is also shown for reference only, although it is visually displayed by the resource monitor (commit value) of Windows 10. (Added on 2020/07/11)

C# NET Core 3.0.100

Use Stack class https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.stack-1?view=netcore-3.1

Memory consumption was 0.39GB.

times Execution time
1st 977 [ms]
2nd 1003 [ms]
3rd 1004 [ms]

From the viewpoint of memory consumption, it seems that int32 is used internally.

It consumes much less memory than other languages and It seems that the small amount of processing data affects the short processing time.

go1.14.4 windows / amd64 (Stack is implemented in 64K segments (array)) (Added 2020/07/17)

The time to end the program was too short for the resource monitor sampling interval, and memory consumption could not be visually confirmed. (0.02GB at the end) Probably the same level as C language.

times Execution time
1st 874 [ms]
2nd 881 [ms]
3rd 904 [ms]

When I implemented it with 64k segments (arrays) similar to C language, the processing time was almost close to that of C language.

It was faster than the C language program as of 2020/07/15, which was compiled with gcc 32bit version, so After that, the C language version is compiled with the MinGW-W64 version and remeasured. (2020/07/17)

go1.14.4 windows / amd64 (array version)

Memory consumption was 2.36GB.

times Execution time
1st 2089 [ms]
2nd 1853 [ms]
3rd 1737 [ms]

Repeated array reassignments don't seem to be too slow. The result is faster than Java.

go1.14.4 windows / amd64 (linear list version)

Memory consumption was 1.49GB.

times Execution time
1st 5617 [ms]
2nd 5400 [ms]
3rd 5569 [ms]

The processing time is slower than the array version.

The linear list needs a pointer to the next node, so Unnecessary data will increase compared to an array with a linear memory arrangement, The result is that it consumes less than the array version.

In Go language, even if you reassign the array The memory may not have been released until the end of the program. (Just guess, I want someone to verify)

java 13.0.2 (Class Stack version)

Use class Stack https://docs.oracle.com/javase/jp/8/docs/api/java/util/Stack.html

Memory consumption was 4.21GB.

times Execution time
1st 6743 [ms]
2nd 6690 [ms]
3rd 6733 [ms]

java 13.0.2 (class ArrayDeque version)

Use class ArrayDeque https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayDeque.html

Memory consumption was 3.96GB.

times Execution time
1st 4397 [ms]
2nd 4612 [ms]
3rd 4477 [ms]

Processing time is shorter than class Stack.

java 13.0.2 (Interface Deque version)

Use interface Deque https://docs.oracle.com/javase/jp/8/docs/api/java/util/Deque.html

Memory consumption was 4.31GB.

times Execution time
1st 21416 [ms]
2nd 20187 [ms]
2nd 20341 [ms]

The processing time has increased compared to the class Stack.

Python 3.8.3

Use list

Memory consumption was 4.42GB.

times Execution time
1st 16957 [ms]
2nd 16561 [ms]
3rd 17558 [ms]

In other languages, the memory once allocated was still consumed, In Python3, the maximum memory consumption is immediately after 100 million pushes. You can see how the memory consumption decreases as the Pop process progresses.

C language (Stack is implemented in 64K segments (array)) (Updated on July 17, 2020)

Memory consumption was 0.38GB.

As expected, C language is fast. I tried to specify -O3 as a compile-time optimization option.

times Execution time
1st 843 [ms]
2nd 828 [ms]
3rd 828 [ms]

By the way, if the memory is not released at the time of pop, the processing time will be as follows.

times Execution time
1st 734 [ms]
2nd 734 [ms]
3rd 734 [ms]

C language (Implementing Stack with linear list) (Updated 17/07/2020)

Memory consumption was 1.55GB.

I tried to specify -O3 as a compile-time optimization option. Since the number of memory allocation / release processes is large, the processing time is slowed down accordingly.

times Execution time
1st 7816 [ms]
2nd 7828 [ms]
3rd 7953 [ms]

Related (Added on 2020/07/11)

There is also a problem with implementing Stack yourself in the LeetCode Problem. Since sample answers in various languages have been posted, it would be interesting to compare the processing times.

Recommended Posts

Stack processing speed comparison by language
Speed comparison of each language by Monte Carlo method
100 Language Processing Knock Chapter 1 by Python
100 Language Processing Knock-89: Analogy by Additive Constitutiveness
Speed comparison when shifting by group by pandas
100 language processing knocks 03 ~ 05
100 language processing knocks (2020): 40
100 language processing knocks (2020): 32
100 language processing knocks (2020): 35
100 language processing knocks (2020): 47
100 language processing knocks (2020): 39
100 language processing knocks (2020): 22
100 language processing knocks (2020): 26
100 language processing knocks (2020): 34
100 Language Processing Knock (2020): 28
100 language processing knocks (2020): 42
100 language processing knocks (2020): 29
100 language processing knocks (2020): 49
100 language processing knocks 06 ~ 09
100 language processing knocks (2020): 43
100 language processing knocks (2020): 24
100 language processing knocks (2020): 45
100 language processing knocks (2020): 10-19
100 language processing knocks (2020): 30
100 language processing knocks (2020): 00-09
100 language processing knocks (2020): 31
100 Language Processing Knock (2020): 38
100 language processing knocks (2020): 48
100 language processing knocks (2020): 44
100 language processing knocks (2020): 41
100 language processing knocks (2020): 37
100 language processing knock 00 ~ 02
100 language processing knocks (2020): 25
100 language processing knocks (2020): 23
100 language processing knocks (2020): 33
100 language processing knocks (2020): 20
100 language processing knocks (2020): 27
100 language processing knocks (2020): 46
100 language processing knocks (2020): 21
100 language processing knocks (2020): 36
100 language processing knock-99 (using pandas): visualization by t-SNE
100 amateur language processing knocks: 41
100 language processing knock 2020 [00 ~ 39 answer]
100 amateur language processing knocks: 56
100 amateur language processing knocks: 24
100 amateur language processing knocks: 50
100 language processing knock 2020 [00-79 answer]
100 language processing knock 2020 [00 ~ 69 answer]
100 amateur language processing knocks: 59
[Language processing 100 knocks 2020] Summary of answer examples by Python
100 amateur language processing knocks: 70
100 amateur language processing knocks: 62
100 amateur language processing knocks: 60
100 Language Processing Knock 2020 Chapter 1
100 amateur language processing knocks: 92
100 amateur language processing knocks: 30
100 Amateur Language Processing Knock: 17
100 amateur language processing knocks: 06
100 amateur language processing knocks: 84
100 language processing knock 2020 [00 ~ 49 answer]
100 amateur language processing knocks: 81