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
diff --git a/include/core/SkTextBlob.h b/include/core/SkTextBlob.h
index 8e67723..8ee1d19 100644
--- a/include/core/SkTextBlob.h
+++ b/include/core/SkTextBlob.h
@@ -53,6 +53,8 @@
kFull_Positioning = 2 // Point positioning -- two scalars per glyph.
};
+ class RunRecord;
+
class RunIterator {
public:
RunIterator(const SkTextBlob* blob);
@@ -68,21 +70,16 @@
GlyphPositioning positioning() const;
private:
- const SkTextBlob* fBlob;
- int fIndex;
+ const RunRecord* fCurrentRun;
+ int fRemainingRuns;
+
+ SkDEBUGCODE(uint8_t* fStorageTop;)
};
- // 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;
- };
+ SkTextBlob(int runCount, const SkRect& bounds);
- SkTextBlob(uint16_t* glyphs, SkScalar* pos, const SkTArray<Run>* runs, const SkRect& bounds);
+ virtual ~SkTextBlob();
+ virtual void internal_dispose() const SK_OVERRIDE;
static unsigned ScalarsPerGlyph(GlyphPositioning pos);
@@ -90,14 +87,14 @@
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 @@
*/
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 @@
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 ee110c7..b815c26 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 @@
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 @@
}
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 @@
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 @@
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 @@
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 (NULL == fRuns) {
- fRuns = SkNEW(SkTArray<SkTextBlob::Run>());
+ if (0 == fRunCount) {
+ SkASSERT(NULL == fStorage.get());
+ SkASSERT(0 == fStorageSize);
+ SkASSERT(0 == fStorageUsed);
+
+ // 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);
- // 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;
+ // reserve may have realloced
+ run = reinterpret_cast<SkTextBlob::RunRecord*>(fStorage.get() + fLastRun);
+ uint32_t preMergeCount = run->glyphCount();
+ run->grow(count);
+
+ // 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 SkTextBlob* SkTextBlobBuilder::build() {
- const SkTextBlob* blob;
+ SkASSERT((fRunCount > 0) == (NULL != fStorage.get()));
- if (fGlyphBuffer.count() > 0) {
- // we have some glyphs, construct a real blob
- SkASSERT(fRuns && !fRuns->empty());
+ this->updateDeferredBounds();
- 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()));
+ 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 70c9ddc..5d08b01 100644
--- a/tests/TextBlobTest.cpp
+++ b/tests/TextBlobTest.cpp
@@ -175,9 +175,6 @@
}
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) {
