[duplicates] enable duplicates analysis in PyCharm/WebStorm/PhpStorm/RubyMine
[idea/community.git] / platform / diff-impl / tests / com / intellij / diff / util / DiffPerformanceTest.kt
1 /*
2  * Copyright 2000-2017 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 package com.intellij.diff.util
18
19 import com.intellij.testFramework.PlatformTestUtil
20 import com.intellij.util.containers.StringInterner
21 import com.intellij.util.diff.Diff
22 import com.intellij.util.diff.FilesTooBigForDiffException
23 import junit.framework.TestCase
24 import java.util.*
25
26 class DiffPerformanceTest : TestCase() {
27   companion object {
28     private var needWarmUp = true
29   }
30
31   private val interner: StringInterner = StringInterner()
32
33   val data = generateData(2000000)
34   private val arr_200000 = data.take(200000).toTypedArray()
35   private val arr_50000 = data.take(50000).toTypedArray()
36   private val arr_20000 = data.take(20000).toTypedArray()
37   private val arr_5000 = data.take(5000).toTypedArray()
38   private val arr_2000 = arr_20000.take(2000).toTypedArray()
39   private val arr_1000 = arr_20000.take(1000).toTypedArray()
40   private val arr_100 = arr_20000.take(100).toTypedArray()
41
42   private val shuffled_2000 = shuffle(arr_2000)
43   private val shuffled_1000 = shuffled_2000.take(1000).toTypedArray()
44   private val shuffled_100 = shuffled_2000.take(100).toTypedArray()
45
46   private val altered_200000 = alter(arr_200000)
47   private val altered_50000 = alter(arr_50000)
48   private val altered_20000 = alter(arr_20000)
49   private val altered_2000 = alter(arr_2000)
50   private val altered_1000 = alter(arr_1000)
51   private val altered_100 = alter(arr_100)
52
53   private val heavy_altered_200000 = heavy_alter(arr_200000)
54   private val heavy_altered_50000 = heavy_alter(arr_50000)
55   private val heavy_altered_20000 = heavy_alter(arr_20000)
56   private val heavy_altered_2000 = heavy_alter(arr_2000)
57   private val heavy_altered_1000 = heavy_alter(arr_1000)
58   private val heavy_altered_100 = heavy_alter(arr_100)
59
60   private val reversed_50000 = arr_50000.reversedArray()
61   private val reversed_5000 = arr_5000.reversedArray()
62   private val reversed_2000 = arr_2000.reversedArray()
63   private val reversed_1000 = arr_1000.reversedArray()
64   private val reversed_100 = arr_100.reversedArray()
65
66   override fun setUp() {
67     if (needWarmUp) {
68       needWarmUp = false
69       warmUp()
70     }
71     super.setUp()
72   }
73
74   private fun warmUp() {
75     for (i in 0..40) {
76       Diff.buildChanges(arr_20000, heavy_altered_20000)
77     }
78   }
79
80   fun `test altered 200000`() {
81     testCpu(3, 550) {
82       Diff.buildChanges(arr_200000, altered_200000)
83     }
84   }
85
86   fun `test heavy altered 200000`() {
87     testCpu(1, 3500) {
88       Diff.buildChanges(arr_200000, heavy_altered_200000)
89     }
90   }
91
92   fun `test reversed 50000 failure`() {
93     testCpu(1, 10_000) {
94       try {
95         Diff.buildChanges(arr_50000, reversed_50000)
96       }
97       catch (e: FilesTooBigForDiffException) {
98         return@testCpu
99       }
100       fail("FilesTooBigForDiffException expected")
101     }
102   }
103
104   fun `test reversed 5000`() {
105     testCpu(1, 2500) {
106       Diff.buildChanges(arr_5000, reversed_5000)
107     }
108   }
109
110   fun `test altered 50000`() {
111     testCpu(20, 650) {
112       Diff.buildChanges(arr_50000, altered_50000)
113     }
114   }
115
116   fun `test heavy altered 50000`() {
117     testCpu(3, 750) {
118       Diff.buildChanges(arr_50000, heavy_altered_50000)
119     }
120   }
121
122   fun `test altered 20000`() {
123     testCpu(20, 350) {
124       Diff.buildChanges(arr_20000, altered_20000)
125     }
126   }
127
128   fun `test heavy altered 20000`() {
129     testCpu(15, 650) {
130       Diff.buildChanges(arr_20000, heavy_altered_20000)
131     }
132   }
133
134   fun `test altered 2000`() {
135     testCpu(400, 550) {
136       Diff.buildChanges(arr_2000, altered_2000)
137     }
138   }
139
140   fun `test heavy altered 2000`() {
141     testCpu(400, 650) {
142       Diff.buildChanges(arr_2000, heavy_altered_2000)
143     }
144   }
145
146   fun `test shuffled 2000`() {
147     testCpu(1, 650) {
148       Diff.buildChanges(arr_2000, shuffled_2000)
149     }
150   }
151
152   fun `test reversed 2000`() {
153     testCpu(1, 550) {
154       Diff.buildChanges(arr_2000, reversed_2000)
155     }
156   }
157
158   fun `test altered 1000`() {
159     testCpu(700, 450) {
160       Diff.buildChanges(arr_1000, altered_1000)
161     }
162   }
163
164   fun `test heavy altered 1000`() {
165     testCpu(700, 550) {
166       Diff.buildChanges(arr_1000, heavy_altered_1000)
167     }
168   }
169
170   fun `test shuffled 1000`() {
171     testCpu(10, 850) {
172       Diff.buildChanges(arr_1000, shuffled_1000)
173     }
174   }
175
176   fun `test reversed 1000`() {
177     testCpu(10, 750) {
178       Diff.buildChanges(arr_1000, reversed_1000)
179     }
180   }
181
182   fun `test altered 100`() {
183     testCpu(10000, 600) {
184       Diff.buildChanges(arr_100, altered_100)
185     }
186   }
187
188   fun `test heavy altered 100`() {
189     testCpu(10000, 650) {
190       Diff.buildChanges(arr_100, heavy_altered_100)
191     }
192   }
193
194   fun `test shuffled 100`() {
195     testCpu(2000, 550) {
196       Diff.buildChanges(arr_100, shuffled_100)
197     }
198   }
199
200   fun `test reversed 100`() {
201     testCpu(1000, 650) {
202       Diff.buildChanges(arr_100, reversed_100)
203     }
204   }
205
206
207   private fun generateData(size: Int): List<String> {
208     return (1..size).map { interner.intern("${it % 200}") }
209   }
210
211   private fun alter(arr: Array<String>): Array<String> {
212     val altered = arr.copyOf()
213     altered[0] = "===" // avoid "common prefix/suffix" optimisation
214     altered[altered.size / 2] = "???"
215     altered[altered.lastIndex] = "==="
216     return altered
217   }
218
219   private fun heavy_alter(arr: Array<String>): Array<String> {
220     val altered = arr.copyOf()
221     for (i in 1..altered.lastIndex step 20) {
222       altered[i] = interner.intern("${i % 200}")
223     }
224     altered[0] = "===" // avoid "common prefix/suffix" optimisation
225     altered[altered.lastIndex] = "==="
226     return altered
227   }
228
229   private fun shuffle(arr: Array<String>): Array<String> {
230     val list = arr.toMutableList()
231     Collections.shuffle(list, Random(0))
232     return list.toTypedArray()
233   }
234
235
236   private inline fun testCpu(iterations: Int, expectedMs: Int, crossinline test: () -> Unit) {
237     PlatformTestUtil.startPerformanceTest(PlatformTestUtil.getTestName(name, true), expectedMs) {
238       for (i in 0..iterations) {
239         test()
240       }
241     }.assertTiming()
242   }
243 }