From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTP id D987E23E1E for ; Fri, 8 Feb 2019 07:52:40 -0500 (EST) Received: from turing.freelists.org ([127.0.0.1]) by localhost (turing.freelists.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ByD-7_NXwiFQ for ; Fri, 8 Feb 2019 07:52:40 -0500 (EST) Received: from smtp46.i.mail.ru (smtp46.i.mail.ru [94.100.177.106]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTPS id EB4AD26D1B for ; Fri, 8 Feb 2019 07:52:39 -0500 (EST) From: Kirill Shcherbatov Subject: [tarantool-patches] [PATCH v1 4/4] sql: got rid of redundant bitmask helpers Date: Fri, 8 Feb 2019 15:52:28 +0300 Message-Id: <6851ecbda131f43e3c704f22799b00b9a021309a.1549629707.git.kshcherbatov@tarantool.org> In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Sender: tarantool-patches-bounce@freelists.org Errors-to: tarantool-patches-bounce@freelists.org Reply-To: tarantool-patches@freelists.org List-help: List-unsubscribe: List-software: Ecartis version 1.0.0 List-Id: tarantool-patches List-subscribe: List-owner: List-post: List-archive: To: tarantool-patches@freelists.org, v.shpilevoy@tarantool.org Cc: Kirill Shcherbatov The original SQLite code allowed the program to be compiled using 32-bit masks to save disk space. Since we are not going to compile Tarantool in such way, we will get rid of these macros by replacing them(where possible) with helpers from column_mask.h Closes #3571 --- src/box/sql/expr.c | 31 ++++++----- src/box/sql/resolve.c | 12 +---- src/box/sql/sqliteInt.h | 24 ++------- src/box/sql/where.c | 110 ++++++++++++++++++---------------------- src/box/sql/whereInt.h | 3 +- 5 files changed, 74 insertions(+), 106 deletions(-) diff --git a/src/box/sql/expr.c b/src/box/sql/expr.c index cf82bd366..613c29bbb 100644 --- a/src/box/sql/expr.c +++ b/src/box/sql/expr.c @@ -2456,19 +2456,20 @@ sqlite3FindInIndex(Parse * pParse, /* Parsing context */ eType == 0; ++k) { struct index *idx = space->index[k]; Bitmask colUsed; /* Columns of the index used */ - Bitmask mCol; /* Mask for the current column */ uint32_t part_count = idx->def->key_def->part_count; struct key_part *parts = idx->def->key_def->parts; if ((int)part_count < nExpr) continue; - /* Maximum nColumn is BMS-2, not BMS-1, so that we can compute - * BITMASK(nExpr) without overflowing + /* + * Maximum nColumn is + * COLUMN_MASK_SIZE-2, not + * COLUMN_MASK_SIZE-1, so that we + * can compute bitmask without + * overflowing. */ - testcase(part_count == BMS - 2); - testcase(part_count == BMS - 1); - if (part_count >= BMS - 1) + if (part_count >= COLUMN_MASK_SIZE - 1) continue; if (mustBeUnique && ((int)part_count > nExpr || @@ -2504,19 +2505,23 @@ sqlite3FindInIndex(Parse * pParse, /* Parsing context */ } if (j == nExpr) break; - mCol = MASKBIT(j); - if (mCol & colUsed) - break; /* Each column used only once */ - colUsed |= mCol; + /* + * Each column used only + * once. + */ + if (column_mask_fieldno_is_set(colUsed, + j)) + break; + column_mask_set_fieldno(&colUsed, j); if (aiMap) aiMap[i] = pRhs->iColumn; else if (pSingleIdxCol && nExpr == 1) *pSingleIdxCol = pRhs->iColumn; } - assert(i == nExpr - || colUsed != (MASKBIT(nExpr) - 1)); - if (colUsed == (MASKBIT(nExpr) - 1)) { + assert(i == nExpr || + colUsed != (COLUMN_MASK_BIT(nExpr) - 1)); + if (colUsed == (COLUMN_MASK_BIT(nExpr) - 1)) { /* If we reach this point, that means the index pIdx is usable */ int iAddr = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v); diff --git a/src/box/sql/resolve.c b/src/box/sql/resolve.c index 1f6ba0418..809771be4 100644 --- a/src/box/sql/resolve.c +++ b/src/box/sql/resolve.c @@ -437,13 +437,8 @@ lookupName(Parse * pParse, /* The parsing context */ * then set the high-order bit of the bitmask. */ if (pExpr->iColumn >= 0 && pMatch != 0) { - int n = pExpr->iColumn; - testcase(n == BMS - 1); - if (n >= BMS) { - n = BMS - 1; - } assert(pMatch->iCursor == pExpr->iTable); - pMatch->colUsed |= ((Bitmask) 1) << n; + column_mask_set_fieldno(&pMatch->colUsed, pExpr->iColumn); } /* Clean up and return @@ -485,10 +480,7 @@ sqlite3CreateColumnExpr(sqlite3 * db, SrcList * pSrc, int iSrc, int iCol) p->space_def = pItem->pTab->def; p->iTable = pItem->iCursor; p->iColumn = (ynVar) iCol; - testcase(iCol == BMS); - testcase(iCol == BMS - 1); - pItem->colUsed |= - ((Bitmask) 1) << (iCol >= BMS ? BMS - 1 : iCol); + column_mask_set_fieldno(&pItem->colUsed, iCol); ExprSetProperty(p, EP_Resolved); } return p; diff --git a/src/box/sql/sqliteInt.h b/src/box/sql/sqliteInt.h index 913d3f9ac..19c9cb3c0 100644 --- a/src/box/sql/sqliteInt.h +++ b/src/box/sql/sqliteInt.h @@ -2286,28 +2286,10 @@ struct IdList { }; /* - * The bitmask datatype defined below is used for various optimizations. - * - * Changing this from a 64-bit to a 32-bit type limits the number of - * tables in a join to 32 instead of 64. But it also reduces the size - * of the library by 738 bytes on ix86. - */ -#ifdef SQLITE_BITMASK_TYPE -typedef SQLITE_BITMASK_TYPE Bitmask; -#else -typedef u64 Bitmask; -#endif - -/* - * The number of bits in a Bitmask. "BMS" means "BitMask Size". - */ -#define BMS ((int)(sizeof(Bitmask)*8)) - -/* - * A bit in a Bitmask + * The bitmask datatype defined below is used for various + * optimizations. */ -#define MASKBIT(n) (((Bitmask)1)<<(n)) -#define ALLBITS ((Bitmask)-1) +typedef uint64_t Bitmask; /* * The following structure describes the FROM clause of a SELECT statement. diff --git a/src/box/sql/where.c b/src/box/sql/where.c index 814bd3926..84470199d 100644 --- a/src/box/sql/where.c +++ b/src/box/sql/where.c @@ -220,7 +220,7 @@ sqlite3WhereGetMask(WhereMaskSet * pMaskSet, int iCursor) assert(pMaskSet->n <= (int)sizeof(Bitmask) * 8); for (i = 0; i < pMaskSet->n; i++) { if (pMaskSet->ix[i] == iCursor) { - return MASKBIT(i); + return COLUMN_MASK_BIT(i); } } return 0; @@ -732,12 +732,10 @@ constructAutomaticIndex(Parse * pParse, /* The parsing context */ int regRecord; /* Register holding an index record */ int n; /* Column counter */ int i; /* Loop counter */ - int mxBitCol; /* Maximum column in pSrc->colUsed */ struct coll *pColl; /* Collating sequence to on a column */ WhereLoop *pLoop; /* The Loop object */ char *zNotUsed; /* Extra space on the end of pIdx */ Bitmask idxCols; /* Bitmap of columns used for indexing */ - Bitmask extraCols; /* Bitmap of additional columns */ u8 sentWarning = 0; /* True if a warnning has been issued */ int iContinue = 0; /* Jump here to skip excluded rows */ struct SrcList_item *pTabItem; /* FROM clause term being indexed */ @@ -763,10 +761,8 @@ constructAutomaticIndex(Parse * pParse, /* The parsing context */ for (pTerm = pWC->a; pTerm < pWCEnd; pTerm++) { if (termCanDriveIndex(pTerm, pSrc, notReady)) { int iCol = pTerm->u.leftColumn; - Bitmask cMask = - iCol >= BMS ? MASKBIT(BMS - 1) : MASKBIT(iCol); - testcase(iCol == BMS); - testcase(iCol == BMS - 1); + uint64_t column_mask; + column_mask_set_fieldno(&column_mask, iCol); if (!sentWarning) { sqlite3_log(SQLITE_WARNING_AUTOINDEX, "automatic index on %s(%s)", @@ -774,13 +770,13 @@ constructAutomaticIndex(Parse * pParse, /* The parsing context */ pTable->aCol[iCol].zName); sentWarning = 1; } - if ((idxCols & cMask) == 0) { + if ((idxCols & column_mask) == 0) { if (whereLoopResize (pParse->db, pLoop, nKeyCol + 1)) { goto end_auto_index_create; } pLoop->aLTerm[nKeyCol++] = pTerm; - idxCols |= cMask; + idxCols |= column_mask; } } } @@ -797,17 +793,17 @@ constructAutomaticIndex(Parse * pParse, /* The parsing context */ * original table changes and the index and table cannot both be used * if they go out of sync. */ - extraCols = pSrc->colUsed & (~idxCols | MASKBIT(BMS - 1)); - mxBitCol = MIN(BMS - 1, pTable->def->field_count); - testcase(pTable->def->field_count == BMS - 1); - testcase(pTable->def->field_count == BMS - 2); - for (i = 0; i < mxBitCol; i++) { - if (extraCols & MASKBIT(i)) + /* Bitmap of additional columns. */ + uint64_t extra_cols = pSrc->colUsed & + (~idxCols | COLUMN_MASK_BIT(COLUMN_MASK_SIZE - 1)); + /* Maximum column in pSrc->colUsed. */ + int max_col_idx = MIN(COLUMN_MASK_SIZE - 1, pTable->def->field_count); + for (i = 0; i < max_col_idx; i++) { + if (column_mask_fieldno_is_set(extra_cols, i)) nKeyCol++; } - if (pSrc->colUsed & MASKBIT(BMS - 1)) { - nKeyCol += pTable->def->field_count - BMS + 1; - } + if (column_mask_is_overflowed(pSrc->colUsed)) + nKeyCol += pTable->def->field_count - COLUMN_MASK_SIZE + 1; /* Construct the Index object to describe this index */ pIdx = sqlite3DbMallocZero(pParse->db, sizeof(*pIdx)); @@ -821,13 +817,11 @@ constructAutomaticIndex(Parse * pParse, /* The parsing context */ for (pTerm = pWC->a; pTerm < pWCEnd; pTerm++) { if (termCanDriveIndex(pTerm, pSrc, notReady)) { int iCol = pTerm->u.leftColumn; - Bitmask cMask = - iCol >= BMS ? MASKBIT(BMS - 1) : MASKBIT(iCol); - testcase(iCol == BMS - 1); - testcase(iCol == BMS); - if ((idxCols & cMask) == 0) { + uint64_t column_mask; + column_mask_set_fieldno(&column_mask, iCol); + if ((idxCols & column_mask) == 0) { Expr *pX = pTerm->pExpr; - idxCols |= cMask; + idxCols |= column_mask; pIdx->aiColumn[n] = pTerm->u.leftColumn; n++; } @@ -838,14 +832,15 @@ constructAutomaticIndex(Parse * pParse, /* The parsing context */ /* Add additional columns needed to make the automatic index into * a covering index */ - for (i = 0; i < mxBitCol; i++) { - if (extraCols & MASKBIT(i)) { + for (i = 0; i < max_col_idx; i++) { + if (column_mask_fieldno_is_set(extra_cols, i)) { pIdx->aiColumn[n] = i; n++; } } - if (pSrc->colUsed & MASKBIT(BMS - 1)) { - for (i = BMS - 1; i < (int)pTable->def->field_count; i++) { + if (column_mask_is_overflowed(pSrc->colUsed)) { + for (i = COLUMN_MASK_SIZE - 1; + i < (int)pTable->def->field_count; i++) { pIdx->aiColumn[n] = i; n++; } @@ -3213,11 +3208,11 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ return 0; nOrderBy = pOrderBy->nExpr; - testcase(nOrderBy == BMS - 1); - if (nOrderBy > BMS - 1) - return 0; /* Cannot optimize overly large ORDER BYs */ + /* Cannot optimize overly large ORDER BYs. */ + if (nOrderBy > COLUMN_MASK_SIZE - 1) + return 0; isOrderDistinct = 1; - obDone = MASKBIT(nOrderBy) - 1; + obDone = COLUMN_MASK_BIT(nOrderBy) - 1; orderDistinctMask = 0; ready = 0; eqOpMask = WO_EQ | WO_ISNULL; @@ -3242,7 +3237,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ * loops. */ for (i = 0; i < nOrderBy; i++) { - if (MASKBIT(i) & obSat) + if (column_mask_fieldno_is_set(obSat, i)) continue; pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr); if (pOBExpr->op != TK_COLUMN) @@ -3282,7 +3277,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ if (coll1 != coll2) continue; } - obSat |= MASKBIT(i); + column_mask_set_fieldno(&obSat, i); } if ((pLoop->wsFlags & WHERE_ONEROW) == 0) { @@ -3381,7 +3376,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ */ isMatch = 0; for (i = 0; bOnce && i < nOrderBy; i++) { - if (MASKBIT(i) & obSat) + if (column_mask_fieldno_is_set(obSat, i)) continue; pOBExpr = sqlite3ExprSkipCollate(pOrderBy-> a[i].pExpr); @@ -3427,14 +3422,15 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ rev = revIdx ^ pOrderBy->a[i]. sort_order; - if (rev) - *pRevMask |= - MASKBIT(iLoop); + if (rev) { + column_mask_set_fieldno( + pRevMask, iLoop); + } revSet = 1; } } if (isMatch) { - obSat |= MASKBIT(i); + column_mask_set_fieldno(&obSat, i); } else { /* No match found */ if (j == 0 || j < nColumn) { @@ -3457,16 +3453,15 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ for (i = 0; i < nOrderBy; i++) { Expr *p; Bitmask mTerm; - if (MASKBIT(i) & obSat) + if (column_mask_fieldno_is_set(obSat, i)) continue; p = pOrderBy->a[i].pExpr; mTerm = sqlite3WhereExprUsage(&pWInfo->sMaskSet, p); if (mTerm == 0 && !sqlite3ExprIsConstant(p)) continue; - if ((mTerm & ~orderDistinctMask) == 0) { - obSat |= MASKBIT(i); - } + if ((mTerm & ~orderDistinctMask) == 0) + column_mask_set_fieldno(&obSat, i); } } } /* End the loop over all WhereLoops from outer-most down to inner-most */ @@ -3474,7 +3469,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ return (i8) nOrderBy; if (!isOrderDistinct) { for (i = nOrderBy - 1; i > 0; i--) { - Bitmask m = MASKBIT(i) - 1; + uint64_t m = COLUMN_MASK_BIT(i) - 1; if ((obSat & m) == m) return i; } @@ -4281,8 +4276,7 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ memset(&sWLB, 0, sizeof(sWLB)); /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */ - testcase(pOrderBy && pOrderBy->nExpr == BMS - 1); - if (pOrderBy && pOrderBy->nExpr >= BMS) + if (pOrderBy && pOrderBy->nExpr >= COLUMN_MASK_SIZE) pOrderBy = 0; sWLB.pOrderBy = pOrderBy; @@ -4296,9 +4290,9 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ /* The number of tables in the FROM clause is limited by the number of * bits in a Bitmask */ - testcase(pTabList->nSrc == BMS); - if (pTabList->nSrc > BMS) { - sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS); + if (pTabList->nSrc > COLUMN_MASK_SIZE) { + sqlite3ErrorMsg(pParse, "at most %d tables in a join", + COLUMN_MASK_SIZE); return 0; } @@ -4400,7 +4394,7 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ for (ii = 0; ii < pTabList->nSrc; ii++) { Bitmask m = sqlite3WhereGetMask(pMaskSet, pTabList->a[ii].iCursor); - assert(m == MASKBIT(ii)); + assert(m == COLUMN_MASK_BIT(ii)); } #endif @@ -4467,7 +4461,7 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ } if (pWInfo->pOrderBy == 0 && (user_session->sql_flags & SQLITE_ReverseOrder) != 0) { - pWInfo->revMask = ALLBITS; + pWInfo->revMask = COLUMN_MASK_FULL; } if (pParse->nErr || NEVER(db->mallocFailed)) { goto whereBeginError; @@ -4574,10 +4568,6 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ space); VdbeComment((v, "%s", space->def->name)); assert(pTabItem->iCursor == pLevel->iTabCur); - testcase(pWInfo->eOnePass == ONEPASS_OFF - && pTab->nCol == BMS - 1); - testcase(pWInfo->eOnePass == ONEPASS_OFF - && pTab->nCol == BMS); sqlite3VdbeChangeP5(v, bFordelete); #ifdef SQLITE_ENABLE_COLUMN_USED_MASK sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, @@ -4668,13 +4658,11 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ continue; if (jj > 63) jj = 63; - if ((pTabItem-> - colUsed & MASKBIT(jj)) == - 0) + if (!column_mask_fieldno_is_set( + &pTabItem->colUsed, i)) continue; - colUsed |= - ((u64) 1) << (ii < - 63 ? ii : 63); + column_mask_set_fieldno(&colUsed, + ii); } sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, iIndexCur, 0, 0, diff --git a/src/box/sql/whereInt.h b/src/box/sql/whereInt.h index 4657055ea..db403ab55 100644 --- a/src/box/sql/whereInt.h +++ b/src/box/sql/whereInt.h @@ -378,7 +378,8 @@ struct WhereAndInfo { */ struct WhereMaskSet { int n; /* Number of assigned cursor values */ - int ix[BMS]; /* Cursor assigned to each bit */ + /* Cursor assigned to each bit. */ + int ix[COLUMN_MASK_SIZE]; }; /* -- 2.20.1