1/* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16package android.support.v7.widget; 17 18import android.support.annotation.Nullable; 19import android.support.v4.os.TraceCompat; 20import android.view.View; 21 22import java.util.ArrayList; 23import java.util.Arrays; 24import java.util.Collections; 25import java.util.Comparator; 26import java.util.concurrent.TimeUnit; 27 28final class GapWorker implements Runnable { 29 30 static final ThreadLocal<GapWorker> sGapWorker = new ThreadLocal<>(); 31 32 ArrayList<RecyclerView> mRecyclerViews = new ArrayList<>(); 33 long mPostTimeNs; 34 long mFrameIntervalNs; 35 36 static class Task { 37 public boolean immediate; 38 public int viewVelocity; 39 public int distanceToItem; 40 public RecyclerView view; 41 public int position; 42 43 public void clear() { 44 immediate = false; 45 viewVelocity = 0; 46 distanceToItem = 0; 47 view = null; 48 position = 0; 49 } 50 } 51 52 /** 53 * Temporary storage for prefetch Tasks that execute in {@link #prefetch(long)}. Task objects 54 * are pooled in the ArrayList, and never removed to avoid allocations, but always cleared 55 * in between calls. 56 */ 57 private ArrayList<Task> mTasks = new ArrayList<>(); 58 59 /** 60 * Prefetch information associated with a specific RecyclerView. 61 */ 62 static class LayoutPrefetchRegistryImpl 63 implements RecyclerView.LayoutManager.LayoutPrefetchRegistry { 64 int mPrefetchDx; 65 int mPrefetchDy; 66 int[] mPrefetchArray; 67 68 int mCount; 69 70 void setPrefetchVector(int dx, int dy) { 71 mPrefetchDx = dx; 72 mPrefetchDy = dy; 73 } 74 75 void collectPrefetchPositionsFromView(RecyclerView view, boolean nested) { 76 mCount = 0; 77 if (mPrefetchArray != null) { 78 Arrays.fill(mPrefetchArray, -1); 79 } 80 81 final RecyclerView.LayoutManager layout = view.mLayout; 82 if (view.mAdapter != null 83 && layout != null 84 && layout.isItemPrefetchEnabled()) { 85 if (nested) { 86 // nested prefetch, only if no adapter updates pending. Note: we don't query 87 // view.hasPendingAdapterUpdates(), as first layout may not have occurred 88 if (!view.mAdapterHelper.hasPendingUpdates()) { 89 layout.collectInitialPrefetchPositions(view.mAdapter.getItemCount(), this); 90 } 91 } else { 92 // momentum based prefetch, only if we trust current child/adapter state 93 if (!view.hasPendingAdapterUpdates()) { 94 layout.collectAdjacentPrefetchPositions(mPrefetchDx, mPrefetchDy, 95 view.mState, this); 96 } 97 } 98 99 if (mCount > layout.mPrefetchMaxCountObserved) { 100 layout.mPrefetchMaxCountObserved = mCount; 101 layout.mPrefetchMaxObservedInInitialPrefetch = nested; 102 view.mRecycler.updateViewCacheSize(); 103 } 104 } 105 } 106 107 @Override 108 public void addPosition(int layoutPosition, int pixelDistance) { 109 if (layoutPosition < 0) { 110 throw new IllegalArgumentException("Layout positions must be non-negative"); 111 } 112 113 if (pixelDistance < 0) { 114 throw new IllegalArgumentException("Pixel distance must be non-negative"); 115 } 116 117 // allocate or expand array as needed, doubling when needed 118 final int storagePosition = mCount * 2; 119 if (mPrefetchArray == null) { 120 mPrefetchArray = new int[4]; 121 Arrays.fill(mPrefetchArray, -1); 122 } else if (storagePosition >= mPrefetchArray.length) { 123 final int[] oldArray = mPrefetchArray; 124 mPrefetchArray = new int[storagePosition * 2]; 125 System.arraycopy(oldArray, 0, mPrefetchArray, 0, oldArray.length); 126 } 127 128 // add position 129 mPrefetchArray[storagePosition] = layoutPosition; 130 mPrefetchArray[storagePosition + 1] = pixelDistance; 131 132 mCount++; 133 } 134 135 boolean lastPrefetchIncludedPosition(int position) { 136 if (mPrefetchArray != null) { 137 final int count = mCount * 2; 138 for (int i = 0; i < count; i += 2) { 139 if (mPrefetchArray[i] == position) return true; 140 } 141 } 142 return false; 143 } 144 145 /** 146 * Called when prefetch indices are no longer valid for cache prioritization. 147 */ 148 void clearPrefetchPositions() { 149 if (mPrefetchArray != null) { 150 Arrays.fill(mPrefetchArray, -1); 151 } 152 mCount = 0; 153 } 154 } 155 156 public void add(RecyclerView recyclerView) { 157 if (RecyclerView.DEBUG && mRecyclerViews.contains(recyclerView)) { 158 throw new IllegalStateException("RecyclerView already present in worker list!"); 159 } 160 mRecyclerViews.add(recyclerView); 161 } 162 163 public void remove(RecyclerView recyclerView) { 164 boolean removeSuccess = mRecyclerViews.remove(recyclerView); 165 if (RecyclerView.DEBUG && !removeSuccess) { 166 throw new IllegalStateException("RecyclerView removal failed!"); 167 } 168 } 169 170 /** 171 * Schedule a prefetch immediately after the current traversal. 172 */ 173 void postFromTraversal(RecyclerView recyclerView, int prefetchDx, int prefetchDy) { 174 if (recyclerView.isAttachedToWindow()) { 175 if (RecyclerView.DEBUG && !mRecyclerViews.contains(recyclerView)) { 176 throw new IllegalStateException("attempting to post unregistered view!"); 177 } 178 if (mPostTimeNs == 0) { 179 mPostTimeNs = recyclerView.getNanoTime(); 180 recyclerView.post(this); 181 } 182 } 183 184 recyclerView.mPrefetchRegistry.setPrefetchVector(prefetchDx, prefetchDy); 185 } 186 187 static Comparator<Task> sTaskComparator = new Comparator<Task>() { 188 @Override 189 public int compare(Task lhs, Task rhs) { 190 // first, prioritize non-cleared tasks 191 if ((lhs.view == null) != (rhs.view == null)) { 192 return lhs.view == null ? 1 : -1; 193 } 194 195 // then prioritize immediate 196 if (lhs.immediate != rhs.immediate) { 197 return lhs.immediate ? -1 : 1; 198 } 199 200 // then prioritize _highest_ view velocity 201 int deltaViewVelocity = rhs.viewVelocity - lhs.viewVelocity; 202 if (deltaViewVelocity != 0) return deltaViewVelocity; 203 204 // then prioritize _lowest_ distance to item 205 int deltaDistanceToItem = lhs.distanceToItem - rhs.distanceToItem; 206 if (deltaDistanceToItem != 0) return deltaDistanceToItem; 207 208 return 0; 209 } 210 }; 211 212 private void buildTaskList() { 213 // Update PrefetchRegistry in each view 214 final int viewCount = mRecyclerViews.size(); 215 int totalTaskCount = 0; 216 for (int i = 0; i < viewCount; i++) { 217 RecyclerView view = mRecyclerViews.get(i); 218 if (view.getWindowVisibility() == View.VISIBLE) { 219 view.mPrefetchRegistry.collectPrefetchPositionsFromView(view, false); 220 totalTaskCount += view.mPrefetchRegistry.mCount; 221 } 222 } 223 224 // Populate task list from prefetch data... 225 mTasks.ensureCapacity(totalTaskCount); 226 int totalTaskIndex = 0; 227 for (int i = 0; i < viewCount; i++) { 228 RecyclerView view = mRecyclerViews.get(i); 229 if (view.getWindowVisibility() != View.VISIBLE) { 230 // Invisible view, don't bother prefetching 231 continue; 232 } 233 234 LayoutPrefetchRegistryImpl prefetchRegistry = view.mPrefetchRegistry; 235 final int viewVelocity = Math.abs(prefetchRegistry.mPrefetchDx) 236 + Math.abs(prefetchRegistry.mPrefetchDy); 237 for (int j = 0; j < prefetchRegistry.mCount * 2; j += 2) { 238 final Task task; 239 if (totalTaskIndex >= mTasks.size()) { 240 task = new Task(); 241 mTasks.add(task); 242 } else { 243 task = mTasks.get(totalTaskIndex); 244 } 245 final int distanceToItem = prefetchRegistry.mPrefetchArray[j + 1]; 246 247 task.immediate = distanceToItem <= viewVelocity; 248 task.viewVelocity = viewVelocity; 249 task.distanceToItem = distanceToItem; 250 task.view = view; 251 task.position = prefetchRegistry.mPrefetchArray[j]; 252 253 totalTaskIndex++; 254 } 255 } 256 257 // ... and priority sort 258 Collections.sort(mTasks, sTaskComparator); 259 } 260 261 static boolean isPrefetchPositionAttached(RecyclerView view, int position) { 262 final int childCount = view.mChildHelper.getUnfilteredChildCount(); 263 for (int i = 0; i < childCount; i++) { 264 View attachedView = view.mChildHelper.getUnfilteredChildAt(i); 265 RecyclerView.ViewHolder holder = RecyclerView.getChildViewHolderInt(attachedView); 266 // Note: can use mPosition here because adapter doesn't have pending updates 267 if (holder.mPosition == position && !holder.isInvalid()) { 268 return true; 269 } 270 } 271 return false; 272 } 273 274 private RecyclerView.ViewHolder prefetchPositionWithDeadline(RecyclerView view, 275 int position, long deadlineNs) { 276 if (isPrefetchPositionAttached(view, position)) { 277 // don't attempt to prefetch attached views 278 return null; 279 } 280 281 RecyclerView.Recycler recycler = view.mRecycler; 282 RecyclerView.ViewHolder holder; 283 try { 284 view.onEnterLayoutOrScroll(); 285 holder = recycler.tryGetViewHolderForPositionByDeadline( 286 position, false, deadlineNs); 287 288 if (holder != null) { 289 if (holder.isBound() && !holder.isInvalid()) { 290 // Only give the view a chance to go into the cache if binding succeeded 291 // Note that we must use public method, since item may need cleanup 292 recycler.recycleView(holder.itemView); 293 } else { 294 // Didn't bind, so we can't cache the view, but it will stay in the pool until 295 // next prefetch/traversal. If a View fails to bind, it means we didn't have 296 // enough time prior to the deadline (and won't for other instances of this 297 // type, during this GapWorker prefetch pass). 298 recycler.addViewHolderToRecycledViewPool(holder, false); 299 } 300 } 301 } finally { 302 view.onExitLayoutOrScroll(false); 303 } 304 return holder; 305 } 306 307 private void prefetchInnerRecyclerViewWithDeadline(@Nullable RecyclerView innerView, 308 long deadlineNs) { 309 if (innerView == null) { 310 return; 311 } 312 313 if (innerView.mDataSetHasChangedAfterLayout 314 && innerView.mChildHelper.getUnfilteredChildCount() != 0) { 315 // RecyclerView has new data, but old attached views. Clear everything, so that 316 // we can prefetch without partially stale data. 317 innerView.removeAndRecycleViews(); 318 } 319 320 // do nested prefetch! 321 final LayoutPrefetchRegistryImpl innerPrefetchRegistry = innerView.mPrefetchRegistry; 322 innerPrefetchRegistry.collectPrefetchPositionsFromView(innerView, true); 323 324 if (innerPrefetchRegistry.mCount != 0) { 325 try { 326 TraceCompat.beginSection(RecyclerView.TRACE_NESTED_PREFETCH_TAG); 327 innerView.mState.prepareForNestedPrefetch(innerView.mAdapter); 328 for (int i = 0; i < innerPrefetchRegistry.mCount * 2; i += 2) { 329 // Note that we ignore immediate flag for inner items because 330 // we have lower confidence they're needed next frame. 331 final int innerPosition = innerPrefetchRegistry.mPrefetchArray[i]; 332 prefetchPositionWithDeadline(innerView, innerPosition, deadlineNs); 333 } 334 } finally { 335 TraceCompat.endSection(); 336 } 337 } 338 } 339 340 private void flushTaskWithDeadline(Task task, long deadlineNs) { 341 long taskDeadlineNs = task.immediate ? RecyclerView.FOREVER_NS : deadlineNs; 342 RecyclerView.ViewHolder holder = prefetchPositionWithDeadline(task.view, 343 task.position, taskDeadlineNs); 344 if (holder != null 345 && holder.mNestedRecyclerView != null 346 && holder.isBound() 347 && !holder.isInvalid()) { 348 prefetchInnerRecyclerViewWithDeadline(holder.mNestedRecyclerView.get(), deadlineNs); 349 } 350 } 351 352 private void flushTasksWithDeadline(long deadlineNs) { 353 for (int i = 0; i < mTasks.size(); i++) { 354 final Task task = mTasks.get(i); 355 if (task.view == null) { 356 break; // done with populated tasks 357 } 358 flushTaskWithDeadline(task, deadlineNs); 359 task.clear(); 360 } 361 } 362 363 void prefetch(long deadlineNs) { 364 buildTaskList(); 365 flushTasksWithDeadline(deadlineNs); 366 } 367 368 @Override 369 public void run() { 370 try { 371 TraceCompat.beginSection(RecyclerView.TRACE_PREFETCH_TAG); 372 373 if (mRecyclerViews.isEmpty()) { 374 // abort - no work to do 375 return; 376 } 377 378 // Query most recent vsync so we can predict next one. Note that drawing time not yet 379 // valid in animation/input callbacks, so query it here to be safe. 380 final int size = mRecyclerViews.size(); 381 long latestFrameVsyncMs = 0; 382 for (int i = 0; i < size; i++) { 383 RecyclerView view = mRecyclerViews.get(i); 384 if (view.getWindowVisibility() == View.VISIBLE) { 385 latestFrameVsyncMs = Math.max(view.getDrawingTime(), latestFrameVsyncMs); 386 } 387 } 388 389 if (latestFrameVsyncMs == 0) { 390 // abort - either no views visible, or couldn't get last vsync for estimating next 391 return; 392 } 393 394 long nextFrameNs = TimeUnit.MILLISECONDS.toNanos(latestFrameVsyncMs) + mFrameIntervalNs; 395 396 prefetch(nextFrameNs); 397 398 // TODO: consider rescheduling self, if there's more work to do 399 } finally { 400 mPostTimeNs = 0; 401 TraceCompat.endSection(); 402 } 403 } 404} 405