IndexedDB: Replace O(n^2) algorithm computing multientry index keys

third_party/WebKit/Source/modules/indexeddb/IDBObjectStore.cpp

 /*
  * Copyright (C) 2010 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  *
  * 1.  Redistributions of source code must retain the above copyright
  *     notice, this list of conditions and the following disclaimer.
  * 2.  Redistributions in binary form must reproduce the above copyright
@@ skipping 312 matching lines @@
 
   if (!indexMetadata.multiEntry || indexKey->getType() != IDBKey::ArrayType) {
     if (!indexKey->isValid())
       return;
 
     indexKeys->push_back(indexKey);
   } else {
     DCHECK(indexMetadata.multiEntry);
     DCHECK_EQ(indexKey->getType(), IDBKey::ArrayType);
     indexKey = IDBKey::createMultiEntryArray(indexKey->array());
-
-    for (size_t i = 0; i < indexKey->array().size(); ++i)
-      indexKeys->push_back(indexKey->array()[i]);
+    indexKeys->appendVector(indexKey->array());

[pwnall, 2017/01/18 02:35:19]

Would it make sense to have IDBKey::createMultiEntryArray return a KeyArray, and
pass the return type directly to appendVector()?

codesearch says that IDBKey::createMultiEntryArray isn't called elsewhere, and
removing the packing/unpacking could let you get rid of some code.
Performance-wise, I'd expect/hope that RVO would make it free to return the
vector directly (no unnecessary copies).

[jsbell, 2017/01/18 18:18:56]

Done; also made it non-static to simplify further.

[pwnall, 2017/01/18 19:04:15]

Cool, nice find!

   }
 }
 
 IDBRequest* IDBObjectStore::add(ScriptState* scriptState,
                                 const ScriptValue& value,
                                 const ScriptValue& key,
                                 ExceptionState& exceptionState) {
   IDB_TRACE("IDBObjectStore::add");
   return put(scriptState, WebIDBPutModeAddOnly, IDBAny::create(this), value,
              key, exceptionState);
@@ skipping 745 matching lines @@
     }
   }
   return IDBIndexMetadata::InvalidId;
 }
 
 WebIDBDatabase* IDBObjectStore::backendDB() const {
   return m_transaction->backendDB();
 }
 
 }  // namespace blink