std::bitset solution for GL Query cache.

gpu/command_buffer/client/query_tracker.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "gpu/command_buffer/client/query_tracker.h"
 
 #include <GLES2/gl2.h>
 #include <GLES2/gl2ext.h>
 #include <GLES2/gl2extchromium.h>
 
 #include <limits.h>
 
 #include "base/atomicops.h"
 #include "base/numerics/safe_conversions.h"
 #include "gpu/command_buffer/client/gles2_cmd_helper.h"
 #include "gpu/command_buffer/client/gles2_implementation.h"
 #include "gpu/command_buffer/client/mapped_memory.h"
 #include "gpu/command_buffer/common/time.h"
 
 namespace gpu {
 namespace gles2 {
 
 QuerySyncManager::Bucket::Bucket(QuerySync* sync_mem,
                                  int32 shm_id,
                                  unsigned int shm_offset)
     : syncs(sync_mem),
       shm_id(shm_id),
       base_shm_offset(shm_offset),
-      free_queries(kSyncsPerBucket) {
-  static_assert(kSyncsPerBucket <= USHRT_MAX,
-                "Can't fit kSyncsPerBucket in unsigned short");
-  for (size_t ii = 0; ii < kSyncsPerBucket; ++ii)
-    free_queries[ii] = ii;
+      in_use_query_count(0),
+      next_query_scan_pos(0) {
 }
 
 QuerySyncManager::Bucket::~Bucket() = default;
 
 QuerySyncManager::QuerySyncManager(MappedMemoryManager* manager)
     : mapped_memory_(manager) {
   DCHECK(manager);
 }
 
 QuerySyncManager::~QuerySyncManager() {
   while (!buckets_.empty()) {
     mapped_memory_->Free(buckets_.front()->syncs);
     delete buckets_.front();
     buckets_.pop_front();
   }
 }
 
 bool QuerySyncManager::Alloc(QuerySyncManager::QueryInfo* info) {
   DCHECK(info);
   Bucket* bucket = nullptr;
   for (Bucket* bucket_candidate : buckets_) {
-    if (!bucket_candidate->free_queries.empty()) {
+    if (bucket_candidate->in_use_query_count != kSyncsPerBucket) {
       bucket = bucket_candidate;
       break;
     }
   }
   if (!bucket) {
     int32 shm_id;
     unsigned int shm_offset;
     void* mem = mapped_memory_->Alloc(
         kSyncsPerBucket * sizeof(QuerySync), &shm_id, &shm_offset);
     if (!mem) {
       return false;
     }
     QuerySync* syncs = static_cast<QuerySync*>(mem);
     bucket = new Bucket(syncs, shm_id, shm_offset);
     buckets_.push_back(bucket);
   }
 
-  unsigned short index_in_bucket = bucket->free_queries.back();
+  unsigned short index_in_bucket = 0;
+  size_t start_and_end_i = bucket->next_query_scan_pos;
+
+  // Find a free Query in the bucket by scanning the bitset of free
+  // flags.  Resume the search where we ended last time to avoid
+  // O(n^2) for the common scenario.

[reveman, 2015/05/18 19:58:42]

is this really worthwhile? i would prefer if we kept this super simply and just
scanned through the bits from the start each time.

+  size_t i = start_and_end_i;
+  do {
+    if (!bucket->in_use_queries[i]) {
+      index_in_bucket = i;
+      bucket->next_query_scan_pos = i;
+      break;
+    }
+    i = (i + 1) % kSyncsPerBucket;
+  } while (i != start_and_end_i);
+
   uint32 shm_offset =
       bucket->base_shm_offset + index_in_bucket * sizeof(QuerySync);
   QuerySync* sync = bucket->syncs + index_in_bucket;
   *info = QueryInfo(bucket, bucket->shm_id, shm_offset, sync);
   info->sync->Reset();
-  bucket->free_queries.pop_back();
+  bucket->in_use_queries[index_in_bucket] = true;
+  bucket->in_use_query_count++;
   return true;
 }
 
 void QuerySyncManager::Free(const QuerySyncManager::QueryInfo& info) {
-  DCHECK(info.bucket->free_queries.size() < kSyncsPerBucket);
+  DCHECK(info.bucket->in_use_query_count > 0);
   unsigned short index_in_bucket = info.sync - info.bucket->syncs;
-  info.bucket->free_queries.push_back(index_in_bucket);
+  DCHECK(info.bucket->in_use_queries[index_in_bucket] == true);
+  info.bucket->in_use_queries[index_in_bucket] = false;
+  info.bucket->in_use_query_count--;
 }
 
 void QuerySyncManager::Shrink() {
   std::deque<Bucket*> new_buckets;
   while (!buckets_.empty()) {
     Bucket* bucket = buckets_.front();
-    if (bucket->free_queries.size() < kSyncsPerBucket) {
+    if (bucket->in_use_query_count > 0) {
       new_buckets.push_back(bucket);
     } else {
       mapped_memory_->Free(bucket->syncs);
       delete bucket;
     }
     buckets_.pop_front();
   }
   buckets_.swap(new_buckets);
 }
 
@@ skipping 163 matching lines @@
     }
 
     query_sync_manager_.Free(query->info_);
     it = removed_queries_.erase(it);
     delete query;
   }
 }
 
 }  // namespace gles2
 }  // namespace gpu