Poor performance during APK decoding when APK contains many duplicate spec names

[wchill]

I am seeing bad performance when decoding GBoard. Log for APKEditor attached at the bottom of this issue, but the issue is with arsclib and not APKEditor.

I believe it has to do with the way duplicate spec names are handled, based on a profiling run:

Details

Renaming duplicate specs is an O(n^2) operation because each rename operation requires first removing the original spec (which causes all entries in the array backing the spec string pool to be copied to remove the hole), then adding the renamed spec (which involves first scanning the entire array to see if it already exists).

❯ java -jar APKEditor-1.4.7.jar d -i com.google.android.inputmethod.latin_16.8.4.867538971-release-x86_64-175666560_minAPI26\(x86_64\)\(nodpi\)_apkmirror.com.apk 
00.000 I: [DECOMPILE] Using: APKEditor version 1.4.7, ARSCLib version 1.3.8
                  -t = xml                                                      
           -load-dex = 3                                                        
            -dex-lib = internal                                                 
      -comment-level = basic                                                    
                  -i = com.google.android.inputmethod.latin_16.8.4.867538971-rel
                     = ease-x86_64-175666560_minAPI26(x86_64)(nodpi)_apkmirror.c
                     = om.apk                                                   
                  -o = com.google.android.inputmethod.latin_16.8.4.867538971-rel
                     = ease-x86_64-175666560_minAPI26(x86_64)(nodpi)_apkmirror.c
                     = om_decompile_xml                                         
 ______________________________________________________________________________ 
00.011 I: [DECOMPILE] Loading ...
00.104 I: [DECOMPILE] Decompiling to xml ...
13.289 I: [DECOMPILE] Initializing android framework ...
13.290 I: [DECOMPILE] Loading android framework for version: 36
13.328 I: [DECOMPILE] Initialized framework: android-36 (16)
13.430 I: [DECOMPILE] [SANITIZE]: Sanitizing paths ...
13.489 I: [DECOMPILE] Validating resource names ...                                                                                                                                                                                                         
04:42.540 I: [DECOMPILE] Spec names validated, duplicates = 31042, bad = 0, removed specs
04:42.540 I: [DECOMPILE] Decode: archive-info.json
04:42.541 I: [DECOMPILE] Decode: uncompressed-files.json
04:42.546 I: [DECOMPILE] Decoding: AndroidManifest.xml
04:42.590 I: [DECOMPILE] public.xml: com.google.android.inputmethod.latin -> package_1
04:42.627 I: [DECOMPILE] Res files: resources
04:45.158 I: [DECOMPILE] Dex files: 3                                                                         
04:45.158 I: [DECOMPILE] Loading full dex files ...
04:45.901 I: [DECOMPILE] Baksmali: v035<8303> classes.dex
04:49.030 I: [DECOMPILE] Baksmali: v035<10611> classes2.dex
04:51.607 I: [DECOMPILE] Baksmali: v035<617> classes3.dex
04:51.893 I: [DECOMPILE] Extracting root files ...
04:51.980 I: [DECOMPILE] Dumping signatures ...
04:51.980 I: [DECOMPILE] Saved to: com.google.android.inputmethod.latin_16.8.4.867538971-release-x86_64-175666560_minAPI26(x86_64)(nodpi)_apkmirror.com_decompile_xml