{"push_id":596086841,"size":1,"distinct_size":1,"ref":"refs/heads/master","head":"f2df8bbb03baf6a236e59c237d11f05ac3f542d3","before":"fa7f01fa343fc465841dc3cfbddd2bd265634b6c","commits":[{"sha":"f2df8bbb03baf6a236e59c237d11f05ac3f542d3","author":{"email":"ef1728e9a9ee178abcf3af44b8924f4f0a6f4047@chromium.org","name":"haraken@chromium.org"},"message":"Oilpan: Optimize an allocation scheme of Vector backing heaps\n\nPerformance of vector backings depends on how much expand and promptlyFree succeeds at an allocation point. This CL increases the succession rate and improves performance. This CL also makes the succession rate less dependent of how caller sites are written (i.e., makes performance more predictable).\n\nCurrently we have two heaps for vectors: VectorHeap and InlineVectorHeap. The assumption here is that InlineVectorHeap is likely to be short-lived and thus it would be better to segregate these two heaps. This assumption is true in some cases but the heuristics leads to unpredictable performance in a lot of cases. For example:\n\nvoid foo() {\n  HeapVector<T> vec1;\n  HeapVector<T, 1> vec2;\n  for (...) {\n    vec1.append(...);\n    vec2.append(...);  // Since vec1 and vec2 are allocated on different heaps, expand() always succeeds at an allocation point. \n  }\n}\n\nis much faster than:\n\nvoid foo() {\n  HeapVector<T> vec1;\n  HeapVector<T> vec2;\n  for (...) {\n    vec1.append(...);\n    vec2.append(...);  // Since vec1 and vec2 are allocated on the same heap, expand() always fails at an allocation point.\n  }\n}\n\nThis kind of performance uncertainty is observed in a bunch of benchmarks. If we replace some Vector with InlineVector, performance can dramatically improve or regress. We should get rid of such uncertainty.\n\nWith that motivation in mind, this CL prepares four heaps for vectors (there is no difference between Vectors and InlineVectors) and choose the \"best\" heap for each vector allocation. To choose the \"best\" heap, we use the following heuristics:\n\n- The goal is to improve the succession rate where expand and promptlyFree happen at an allocation point.\n- A vector that has been expanded is likely to be expanded again soon.\n- A vector is likely to be promptly freed if the same type of vector has been frequently promptly freed in the past.\n- When allocating a new vector, look at the (four) vectors that are placed immediately prior to the allocation point of each heap. Choose the heap where the vector is least likely to be expanded and promptly freed.\n\nTo realize the algorithm, we introduce a timestamp to each heap. The timestamp is updated if:\n\n- a vector on the heap is expanded; or\n- a vector that meets the condition (*) is allocated on the heap\n\n(*) More than 33% of the same type of vectors have been promptly freed since the last GC\n\nWhen allocating a new vector, we can just choose a heap that has the smallest timestamp. Specifically, we use the following data structures:\n\n- ThreadState::m_vectorBackingHeapIndex: Points to the heap that has the smallest timestamp.\n- ThreadState::m_timestamps[NumberOfHeaps]: Keeps track of the timestamp of each heap.\n- ThreadState::m_likelyToBePromptlyFreed[gcInfoTableMax]: Keeps track of how frequently the vector type is promptly freed. If the number is larger than 0, it means that more than 33% of the same type of vectors have been promptly freed since the last GC. (A more straightforward implementation would be just to use m_promptlyFreedCount[] and m_allocatedCount[], but we cannot do that in order not to access two arrays in ThreadState::vectorBackingHeap, where performance matters.)\n\n\nBUG=420515\n\nCommitted: https://src.chromium.org/viewvc/blink?view=rev&revision=191520\n\nReview URL: https://codereview.chromium.org/856353003\n\ngit-svn-id: svn://svn.chromium.org/blink/trunk@191548 bbb929c8-8fbe-4397-9dbb-9b2b20218538","distinct":true,"url":"https://api.github.com/repos/dstockwell/blink/commits/f2df8bbb03baf6a236e59c237d11f05ac3f542d3"}]}