Add benchmark for property mapping
This benchmarks mapping property prefixes to property contexts with
two algorithms: the 'Legacy' method used before Android P and the
'Trie' used afterwards (the code in this directory).
It uses input mappings from both Oreo and the latest in AOSP ('S').
Note that there is nearly a 10x increase in the number of mappings in
S as there was in Oreo, which was predicted when the trie was
designed.
Results on cuttlefish:
-----------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------
LegacyLookupOreo 683576 ns 673538 ns 1060
LegacyLookupS 5683109 ns 5596982 ns 124
TrieLookupOreo 299851 ns 295696 ns 2378
TrieLookupS 584831 ns 576801 ns 1204
The results show that the legacy look up uses 8.3x more CPU time to
handle the number of mappings added through S, whereas the Trie lookup
uses less than 2x more CPU time, showing that the trie scales better
with added mappings.
Test: run this benchmark
Change-Id: I35c3aa4429f049e327a891f9cbe1901d8855d7ba
diff --git a/libc/NOTICE b/libc/NOTICE
index e8dc4e7..58d6679 100644
--- a/libc/NOTICE
+++ b/libc/NOTICE
@@ -1040,6 +1040,22 @@
-------------------------------------------------------------------
Copyright (C) 2020 The Android Open Source Project
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+
+-------------------------------------------------------------------
+
+Copyright (C) 2020 The Android Open Source Project
All rights reserved.
Redistribution and use in source and binary forms, with or without