diff options
author | fmalita <fmalita@chromium.org> | 2014-09-20 05:40:22 -0700 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2014-09-20 05:40:22 -0700 |
commit | 3c196def91726913a417e703ac482bb2dbbfff27 (patch) | |
tree | d705d2d7ad765bd7918982440e762883224d4358 | |
parent | a56d1d8889e9f2ccdeb9b08d7e719426167bc69d (diff) |
Souped-up SkTextBlob.
Refactored text blob backend for improved performance: instead of using
separate buffers for runs/positions/glyphs, everything is now packed in
a consolidated slab (including the SkTextBlob object itself!).
Benefits:
* number of allocations per blob construction reduced from ~4 to 1
(also minimizes internal fragmentation)
* run record size reduced by 8 bytes
This takes the blob construction overhead down to negligible levels
(for the current Blink uncached textblob implementation).
Unfortunately, the code is much more finicky (run merging in
particular) -- hence the assert spree.
Multi-run blobs are vulnerable to realloc storms but this is not a
problem at the moment because Blink is using one-run blobs 99% of the
time. Will be addressed in the future.
R=mtklein@google.com, reed@google.com, robertphillips@google.com
Committed: https://skia.googlesource.com/skia/+/13645ea0ea87038ebd71be3bd6d53b313069a9e4
Author: fmalita@chromium.org
Review URL: https://codereview.chromium.org/581173003
-rw-r--r-- | include/core/SkTextBlob.h | 58 | ||||
-rw-r--r-- | src/core/SkTextBlob.cpp | 350 | ||||
-rw-r--r-- | tests/TextBlobTest.cpp | 3 |
3 files changed, 285 insertions, 126 deletions
diff --git a/include/core/SkTextBlob.h b/include/core/SkTextBlob.h index 8e67723494..8ee1d19196 100644 --- a/include/core/SkTextBlob.h +++ b/include/core/SkTextBlob.h @@ -53,6 +53,8 @@ private: kFull_Positioning = 2 // Point positioning -- two scalars per glyph. }; + class RunRecord; + class RunIterator { public: RunIterator(const SkTextBlob* blob); @@ -68,21 +70,16 @@ private: GlyphPositioning positioning() const; private: - const SkTextBlob* fBlob; - int fIndex; - }; + const RunRecord* fCurrentRun; + int fRemainingRuns; - // A run is a sequence of glyphs sharing the same font metrics and positioning mode. - struct Run { - uint32_t count; - uint32_t glyphStart; // index into fGlyphBuffer - uint32_t posStart; // index into fPosBuffer - SkPoint offset; // run offset (unsued for fully positioned glyphs) - SkPaint font; - GlyphPositioning positioning; + SkDEBUGCODE(uint8_t* fStorageTop;) }; - SkTextBlob(uint16_t* glyphs, SkScalar* pos, const SkTArray<Run>* runs, const SkRect& bounds); + SkTextBlob(int runCount, const SkRect& bounds); + + virtual ~SkTextBlob(); + virtual void internal_dispose() const SK_OVERRIDE; static unsigned ScalarsPerGlyph(GlyphPositioning pos); @@ -90,14 +87,14 @@ private: friend class SkTextBlobBuilder; friend class TextBlobTester; - const SkAutoTMalloc<uint16_t> fGlyphBuffer; - const SkAutoTMalloc<SkScalar> fPosBuffer; + const int fRunCount; + const SkRect fBounds; + mutable uint32_t fUniqueID; - // SkTArray required here for run font destruction. - SkAutoTDelete<const SkTArray<Run> > fRuns; - const SkRect fBounds; + SkDEBUGCODE(size_t fStorageSize;) - mutable uint32_t fUniqueID; + // The actual payload resides in externally-managed storage, following the object. + // (see the .cpp for more details) typedef SkRefCnt INHERITED; }; @@ -108,11 +105,7 @@ private: */ class SK_API SkTextBlobBuilder { public: - /** - * @param runs The number of runs to be added, if known. This is a storage hint and - * not a limit. - */ - SkTextBlobBuilder(unsigned runs = 0); + SkTextBlobBuilder(); ~SkTextBlobBuilder(); @@ -180,20 +173,23 @@ public: const RunBuffer& allocRunPos(const SkPaint& font, int count, const SkRect* bounds = NULL); private: + void reserve(size_t size); void allocInternal(const SkPaint& font, SkTextBlob::GlyphPositioning positioning, int count, SkPoint offset, const SkRect* bounds); - void ensureRun(const SkPaint& font, SkTextBlob::GlyphPositioning positioning, - const SkPoint& offset); + bool mergeRun(const SkPaint& font, SkTextBlob::GlyphPositioning positioning, + int count, SkPoint offset); void updateDeferredBounds(); - SkTDArray<uint16_t> fGlyphBuffer; - SkTDArray<SkScalar> fPosBuffer; - SkTArray<SkTextBlob::Run>* fRuns; + SkAutoTMalloc<uint8_t> fStorage; + size_t fStorageSize; + size_t fStorageUsed; - SkRect fBounds; - bool fDeferredBounds; + SkRect fBounds; + int fRunCount; + bool fDeferredBounds; + size_t fLastRun; // index into fStorage - RunBuffer fCurrentRunBuffer; + RunBuffer fCurrentRunBuffer; }; #endif // SkTextBlob_DEFINED diff --git a/src/core/SkTextBlob.cpp b/src/core/SkTextBlob.cpp index ee110c7d07..b815c263a8 100644 --- a/src/core/SkTextBlob.cpp +++ b/src/core/SkTextBlob.cpp @@ -10,14 +10,125 @@ #include "SkReadBuffer.h" #include "SkWriteBuffer.h" -SkTextBlob::SkTextBlob(uint16_t *glyphs, SkScalar *pos, const SkTArray<Run> *runs, - const SkRect& bounds) - : fGlyphBuffer(glyphs) - , fPosBuffer(pos) - , fRuns(runs) +// +// Textblob data is laid out into externally-managed storage as follows: +// +// ----------------------------------------------------------------------------- +// | SkTextBlob | RunRecord | Glyphs[] | Pos[] | RunRecord | Glyphs[] | Pos[] | ... +// ----------------------------------------------------------------------------- +// +// Each run record describes a text blob run, and can be used to determine the (implicit) +// location of the following record. + +SkDEBUGCODE(static const unsigned kRunRecordMagic = 0xb10bcafe;) + +class SkTextBlob::RunRecord { +public: + RunRecord(uint32_t count, const SkPoint& offset, const SkPaint& font, GlyphPositioning pos) + : fCount(count) + , fOffset(offset) + , fFont(font) + , fPositioning(pos) { + SkDEBUGCODE(fMagic = kRunRecordMagic); + } + + uint32_t glyphCount() const { + return fCount; + } + + const SkPoint& offset() const { + return fOffset; + } + + const SkPaint& font() const { + return fFont; + } + + GlyphPositioning positioning() const { + return fPositioning; + } + + uint16_t* glyphBuffer() const { + // Glyph are stored immediately following the record. + return reinterpret_cast<uint16_t*>(const_cast<RunRecord*>(this) + 1); + } + + SkScalar* posBuffer() const { + // Position scalars follow the (aligned) glyph buffer. + return reinterpret_cast<SkScalar*>(reinterpret_cast<uint8_t*>(this->glyphBuffer()) + + SkAlign4(fCount * sizeof(uint16_t))); + } + + static size_t StorageSize(int glyphCount, SkTextBlob::GlyphPositioning positioning) { + // RunRecord object + (aligned) glyph buffer + position buffer + return SkAlignPtr(sizeof(SkTextBlob::RunRecord) + + SkAlign4(glyphCount* sizeof(uint16_t)) + + glyphCount * sizeof(SkScalar) * ScalarsPerGlyph(positioning)); + } + + static const RunRecord* First(const SkTextBlob* blob) { + // The first record (if present) is stored following the blob object. + return reinterpret_cast<const RunRecord*>(blob + 1); + } + + static const RunRecord* Next(const RunRecord* run) { + return reinterpret_cast<const RunRecord*>(reinterpret_cast<const uint8_t*>(run) + + StorageSize(run->glyphCount(), run->positioning())); + } + + void validate(uint8_t* storageTop) const { + SkASSERT(kRunRecordMagic == fMagic); + SkASSERT((uint8_t*)Next(this) <= storageTop); + SkASSERT(glyphBuffer() + fCount <= (uint16_t*)posBuffer()); + SkASSERT(posBuffer() + fCount * ScalarsPerGlyph(fPositioning) <= (SkScalar*)Next(this)); + } + +private: + friend class SkTextBlobBuilder; + + void grow(uint32_t count) { + SkScalar* initialPosBuffer = posBuffer(); + uint32_t initialCount = fCount; + fCount += count; + + // Move the initial pos scalars to their new location. + size_t copySize = initialCount * sizeof(SkScalar) * ScalarsPerGlyph(fPositioning); + SkASSERT((uint8_t*)posBuffer() + copySize <= (uint8_t*)Next(this)); + + // memmove, as the buffers may overlap + memmove(posBuffer(), initialPosBuffer, copySize); + } + + uint32_t fCount; + SkPoint fOffset; + SkPaint fFont; + GlyphPositioning fPositioning; + + SkDEBUGCODE(unsigned fMagic;) +}; + +SkTextBlob::SkTextBlob(int runCount, const SkRect& bounds) + : fRunCount(runCount) , fBounds(bounds) { } +SkTextBlob::~SkTextBlob() { + const RunRecord* run = RunRecord::First(this); + for (int i = 0; i < fRunCount; ++i) { + const RunRecord* nextRun = RunRecord::Next(run); + SkDEBUGCODE(run->validate((uint8_t*)this + fStorageSize);) + run->~RunRecord(); + run = nextRun; + } +} + +void SkTextBlob::internal_dispose() const { + // SkTextBlobs use externally-managed storage. + this->internal_dispose_restore_refcnt_to_1(); + this->~SkTextBlob(); + sk_free(const_cast<SkTextBlob*>(this)); +} + uint32_t SkTextBlob::uniqueID() const { static int32_t gTextBlobGenerationID; // = 0; @@ -29,14 +140,8 @@ uint32_t SkTextBlob::uniqueID() const { return fUniqueID; } -unsigned SkTextBlob::ScalarsPerGlyph(GlyphPositioning pos) { - // GlyphPositioning values are directly mapped to scalars-per-glyph. - SkASSERT(pos <= 2); - return pos; -} - void SkTextBlob::flatten(SkWriteBuffer& buffer) const { - int runCount = (NULL == fRuns.get()) ? 0 : fRuns->count(); + int runCount = fRunCount; buffer.write32(runCount); buffer.writeRect(fBounds); @@ -101,7 +206,8 @@ const SkTextBlob* SkTextBlob::CreateFromBuffer(SkReadBuffer& reader) { } if (!reader.readByteArray(buf->glyphs, glyphCount * sizeof(uint16_t)) || - !reader.readByteArray(buf->pos, glyphCount * sizeof(SkScalar) * ScalarsPerGlyph(pos))) { + !reader.readByteArray(buf->pos, + glyphCount * sizeof(SkScalar) * ScalarsPerGlyph(pos))) { return NULL; } } @@ -109,50 +215,61 @@ const SkTextBlob* SkTextBlob::CreateFromBuffer(SkReadBuffer& reader) { return blobBuilder.build(); } +unsigned SkTextBlob::ScalarsPerGlyph(GlyphPositioning pos) { + // GlyphPositioning values are directly mapped to scalars-per-glyph. + SkASSERT(pos <= 2); + return pos; +} + SkTextBlob::RunIterator::RunIterator(const SkTextBlob* blob) - : fBlob(blob) - , fIndex(0) { - SkASSERT(blob); + : fCurrentRun(RunRecord::First(blob)) + , fRemainingRuns(blob->fRunCount) { + SkDEBUGCODE(fStorageTop = (uint8_t*)blob + blob->fStorageSize;) } bool SkTextBlob::RunIterator::done() const { - return NULL == fBlob->fRuns.get() || fIndex >= fBlob->fRuns->count(); + return fRemainingRuns <= 0; } void SkTextBlob::RunIterator::next() { SkASSERT(!this->done()); - fIndex++; + + if (!this->done()) { + SkDEBUGCODE(fCurrentRun->validate(fStorageTop);) + fCurrentRun = RunRecord::Next(fCurrentRun); + fRemainingRuns--; + } } uint32_t SkTextBlob::RunIterator::glyphCount() const { SkASSERT(!this->done()); - return (*fBlob->fRuns)[fIndex].count; + return fCurrentRun->glyphCount(); } const uint16_t* SkTextBlob::RunIterator::glyphs() const { SkASSERT(!this->done()); - return fBlob->fGlyphBuffer.get() + (*fBlob->fRuns)[fIndex].glyphStart; + return fCurrentRun->glyphBuffer(); } const SkScalar* SkTextBlob::RunIterator::pos() const { SkASSERT(!this->done()); - return fBlob->fPosBuffer.get() + (*fBlob->fRuns)[fIndex].posStart; + return fCurrentRun->posBuffer(); } const SkPoint& SkTextBlob::RunIterator::offset() const { SkASSERT(!this->done()); - return (*fBlob->fRuns)[fIndex].offset; + return fCurrentRun->offset(); } SkTextBlob::GlyphPositioning SkTextBlob::RunIterator::positioning() const { SkASSERT(!this->done()); - return (*fBlob->fRuns)[fIndex].positioning; + return fCurrentRun->positioning(); } void SkTextBlob::RunIterator::applyFontToPaint(SkPaint* paint) const { SkASSERT(!this->done()); - const SkPaint& font = (*fBlob->fRuns)[fIndex].font; + const SkPaint& font = fCurrentRun->font(); paint->setTypeface(font.getTypeface()); paint->setTextEncoding(font.getTextEncoding()); @@ -177,24 +294,25 @@ void SkTextBlob::RunIterator::applyFontToPaint(SkPaint* paint) const { paint->setFlags((paint->getFlags() & ~flagsMask) | (font.getFlags() & flagsMask)); } -SkTextBlobBuilder::SkTextBlobBuilder(unsigned runs) - : fRuns(NULL) - , fDeferredBounds(false) { - - if (runs > 0) { - // if the number of runs is known, size our run storage accordingly. - fRuns = SkNEW(SkTArray<SkTextBlob::Run>(runs)); - } +SkTextBlobBuilder::SkTextBlobBuilder() + : fStorageSize(0) + , fStorageUsed(0) + , fRunCount(0) + , fDeferredBounds(false) + , fLastRun(0) { fBounds.setEmpty(); } SkTextBlobBuilder::~SkTextBlobBuilder() { - // unused runs - SkDELETE(fRuns); + if (NULL != fStorage.get()) { + // We are abandoning runs and must destruct the associated font data. + // The easiest way to accomplish that is to use the blob destructor. + build()->unref(); + } } void SkTextBlobBuilder::updateDeferredBounds() { - SkASSERT(!fDeferredBounds || (fRuns && !fRuns->empty())); + SkASSERT(!fDeferredBounds || fRunCount > 0); if (!fDeferredBounds) { return; @@ -204,64 +322,104 @@ void SkTextBlobBuilder::updateDeferredBounds() { fDeferredBounds = false; } -void SkTextBlobBuilder::ensureRun(const SkPaint& font, SkTextBlob::GlyphPositioning pos, - const SkPoint& offset) { - SkASSERT(SkPaint::kGlyphID_TextEncoding == font.getTextEncoding()); +void SkTextBlobBuilder::reserve(size_t size) { + // We don't currently pre-allocate, but maybe someday... + if (fStorageUsed + size <= fStorageSize) { + return; + } + + if (0 == fRunCount) { + SkASSERT(NULL == fStorage.get()); + SkASSERT(0 == fStorageSize); + SkASSERT(0 == fStorageUsed); - if (NULL == fRuns) { - fRuns = SkNEW(SkTArray<SkTextBlob::Run>()); + // the first allocation also includes blob storage + fStorageUsed += sizeof(SkTextBlob); + } + + fStorageSize = fStorageUsed + size; + // FYI: This relies on everything we store being relocatable, particularly SkPaint. + fStorage.realloc(fStorageSize); +} + +bool SkTextBlobBuilder::mergeRun(const SkPaint &font, SkTextBlob::GlyphPositioning positioning, + int count, SkPoint offset) { + if (0 == fLastRun) { + SkASSERT(0 == fRunCount); + return false; + } + + SkASSERT(fLastRun >= sizeof(SkTextBlob)); + SkTextBlob::RunRecord* run = reinterpret_cast<SkTextBlob::RunRecord*>(fStorage.get() + + fLastRun); + SkASSERT(run->glyphCount() > 0); + + if (run->positioning() != positioning + || run->font() != font + || (run->glyphCount() + count < run->glyphCount())) { + return false; } // we can merge same-font/same-positioning runs in the following cases: // * fully positioned run following another fully positioned run // * horizontally postioned run following another horizontally positioned run with the same // y-offset - if (!fRuns->empty() - && fRuns->back().positioning == pos - && fRuns->back().font == font - && (SkTextBlob::kFull_Positioning == fRuns->back().positioning - || (SkTextBlob::kHorizontal_Positioning == fRuns->back().positioning - && fRuns->back().offset.y() == offset.y()))){ - return; + if (SkTextBlob::kFull_Positioning != positioning + && (SkTextBlob::kHorizontal_Positioning != positioning + || run->offset().y() != offset.y())) { + return false; } - this->updateDeferredBounds(); + size_t sizeDelta = SkTextBlob::RunRecord::StorageSize(run->glyphCount() + count, positioning) - + SkTextBlob::RunRecord::StorageSize(run->glyphCount(), positioning); + this->reserve(sizeDelta); + + // reserve may have realloced + run = reinterpret_cast<SkTextBlob::RunRecord*>(fStorage.get() + fLastRun); + uint32_t preMergeCount = run->glyphCount(); + run->grow(count); - // start a new run - SkTextBlob::Run& newRun = fRuns->push_back(); - newRun.count = 0; - newRun.glyphStart = fGlyphBuffer.count(); - newRun.posStart = fPosBuffer.count(); - newRun.offset = offset; - newRun.font = font; - newRun.positioning = pos; + // Callers expect the buffers to point at the newly added slice, ant not at the beginning. + fCurrentRunBuffer.glyphs = run->glyphBuffer() + preMergeCount; + fCurrentRunBuffer.pos = run->posBuffer() + + preMergeCount * SkTextBlob::ScalarsPerGlyph(positioning); + + fStorageUsed += sizeDelta; + + SkASSERT(fStorageUsed <= fStorageSize); + run->validate(fStorage.get() + fStorageUsed); + + return true; } void SkTextBlobBuilder::allocInternal(const SkPaint &font, SkTextBlob::GlyphPositioning positioning, int count, SkPoint offset, const SkRect* bounds) { SkASSERT(count > 0); + SkASSERT(SkPaint::kGlyphID_TextEncoding == font.getTextEncoding()); - this->ensureRun(font, positioning, offset); + if (!this->mergeRun(font, positioning, count, offset)) { + updateDeferredBounds(); - unsigned posScalarsPerGlyph = SkTextBlob::ScalarsPerGlyph(positioning); + size_t runSize = SkTextBlob::RunRecord::StorageSize(count, positioning); + this->reserve(runSize); - fGlyphBuffer.append(count); - fPosBuffer.append(count * posScalarsPerGlyph); + SkASSERT(fStorageUsed >= sizeof(SkTextBlob)); + SkASSERT(fStorageUsed + runSize <= fStorageSize); - SkASSERT(fRuns && !fRuns->empty()); - SkTextBlob::Run& run = fRuns->back(); + SkTextBlob::RunRecord* run = new (fStorage.get() + fStorageUsed) + SkTextBlob::RunRecord(count, offset, font, positioning); - run.count += count; + fCurrentRunBuffer.glyphs = run->glyphBuffer(); + fCurrentRunBuffer.pos = run->posBuffer(); - // The current run might have been merged, so the start offset may point to prev run data. - // Start from the back (which always points to the end of the current run buffers) instead. - fCurrentRunBuffer.glyphs = fGlyphBuffer.isEmpty() - ? NULL : fGlyphBuffer.end() - count; - SkASSERT(NULL == fCurrentRunBuffer.glyphs || fCurrentRunBuffer.glyphs >= fGlyphBuffer.begin()); - fCurrentRunBuffer.pos = fPosBuffer.isEmpty() - ? NULL : fPosBuffer.end() - count * posScalarsPerGlyph; - SkASSERT(NULL == fCurrentRunBuffer.pos || fCurrentRunBuffer.pos >= fPosBuffer.begin()); + fLastRun = fStorageUsed; + fStorageUsed += runSize; + fRunCount++; + + SkASSERT(fStorageUsed <= fStorageSize); + run->validate(fStorage.get() + fStorageUsed); + } if (!fDeferredBounds) { if (bounds) { @@ -297,29 +455,37 @@ const SkTextBlobBuilder::RunBuffer& SkTextBlobBuilder::allocRunPos(const SkPaint } const SkTextBlob* SkTextBlobBuilder::build() { - const SkTextBlob* blob; - - if (fGlyphBuffer.count() > 0) { - // we have some glyphs, construct a real blob - SkASSERT(fRuns && !fRuns->empty()); - - this->updateDeferredBounds(); - - // ownership of all buffers is transferred to the blob - blob = SkNEW_ARGS(SkTextBlob, (fGlyphBuffer.detach(), - fPosBuffer.detach(), - fRuns, - fBounds)); - fRuns = NULL; - fBounds.setEmpty(); - } else { - // empty blob - SkASSERT(NULL == fRuns || fRuns->empty()); - SkASSERT(fBounds.isEmpty()); - - blob = SkNEW_ARGS(SkTextBlob, (NULL, NULL, NULL, SkRect::MakeEmpty())); + SkASSERT((fRunCount > 0) == (NULL != fStorage.get())); + + this->updateDeferredBounds(); + + if (0 == fRunCount) { + SkASSERT(NULL == fStorage.get()); + fStorageUsed = sizeof(SkTextBlob); + fStorage.realloc(fStorageUsed); } + SkDEBUGCODE( + size_t validateSize = sizeof(SkTextBlob); + const SkTextBlob::RunRecord* run = + SkTextBlob::RunRecord::First(reinterpret_cast<const SkTextBlob*>(fStorage.get())); + for (int i = 0; i < fRunCount; ++i) { + validateSize += SkTextBlob::RunRecord::StorageSize(run->fCount, run->fPositioning); + run->validate(fStorage.get() + fStorageUsed); + run = SkTextBlob::RunRecord::Next(run); + } + SkASSERT(validateSize == fStorageUsed); + ) + + const SkTextBlob* blob = new (fStorage.detach()) SkTextBlob(fRunCount, fBounds); + SkDEBUGCODE(const_cast<SkTextBlob*>(blob)->fStorageSize = fStorageSize;) + + fStorageUsed = 0; + fStorageSize = 0; + fRunCount = 0; + fLastRun = 0; + fBounds.setEmpty(); + return blob; } diff --git a/tests/TextBlobTest.cpp b/tests/TextBlobTest.cpp index 70c9ddc861..5d08b0147d 100644 --- a/tests/TextBlobTest.cpp +++ b/tests/TextBlobTest.cpp @@ -175,9 +175,6 @@ private: } SkAutoTUnref<const SkTextBlob> blob(builder.build()); - REPORTER_ASSERT(reporter, SkToBool(blob->fGlyphBuffer) == (glyphCount > 0)); - REPORTER_ASSERT(reporter, SkToBool(blob->fPosBuffer) == (posCount > 0)); - REPORTER_ASSERT(reporter, SkToBool(blob->fRuns.get()) == (inCount > 0)); SkTextBlob::RunIterator it(blob); for (unsigned i = 0; i < outCount; ++i) { |