Found a few issues with the first diff, with corrections attached:
* Remapping the array of category ids using a new dictionary in place was
causing SIGSEGV because the array was mmapped to the *.ids file. remap must
use a copy of the array
* Ownership of common dictionaries need to be moved to the ibis::bord
instance that is returned to prevent them from being deleted
* Off-By-One error when merging dictionaries; dictionary index runs from
[0,dic::size] rather than [0::dic::size-1]
From: "Enns, Steven" <[email protected]<mailto:[email protected]>>
Date: Friday, October 16, 2015 at 10:36 PM
To: FastBit Users
<[email protected]<mailto:[email protected]>>
Subject: suggested optimization for groupBy on multi-part category columns
Hi John,
We noticed that a simple group by query took disproportionately long on
multiple partitions compared to a single partition. The profiler indicates
that the bottleneck is in converting the original column from ids to strings
(lots of string allocs), and then the group by operations (sort, reduce) are
done on strings instead of the category ids. The reason for the string
conversion seems to be that the ids aren't consistent across the partitions.
Instead I propose re-mapping the ids into a shared dictionary in
ibis::bord::column::append. The diff is attached, we observe about 5x-10x
speedup depending on the number of columns in the group-by.
Steve
diff --git a/fastbit/fastbit-ibis1.3.5/src/bord.cpp
b/fastbit/fastbit-ibis1.3.5/src/bord.cpp
index e43d90c..1ce2c13 100755
--- a/fastbit/fastbit-ibis1.3.5/src/bord.cpp
+++ b/fastbit/fastbit-ibis1.3.5/src/bord.cpp
@@ -448,10 +448,25 @@ ibis::bord::bord(const char *tn, const char *td,
ibis::bord::column *col = new ibis::bord::column
(this, t, cname, 0, sc.aggName(j));
if (col != 0) {
- if (refcol->type() == ibis::CATEGORY &&
- t == ibis::UINT) {
+ if (refcol->type() == ibis::CATEGORY && t ==
ibis::UINT) {
col->loadIndex();
- col->setDictionary(refcol->getDictionary());
+ if (ref.size() == 1) {
+ col->setDictionary(refcol->getDictionary());
+ } else {
+ // multiple partitions with (presumably)
distinct dictionaries.
+ // merge them together into a common
dictionary so that aggregate
+ // operations can be performed on category ids
rather than strings
+ std::unique_ptr<ibis::dictionary>
common_dic(new ibis::dictionary());
+ for (unsigned i = 0; i < ref.size(); ++ i) {
+ const ibis::column *col1 =
ref[i]->getColumn(refcol->name());
+ if (col1 != 0) {
+ const ibis::dictionary *dic1 =
col1->getDictionary();
+ common_dic->merge(*dic1);
+ }
+ }
+ col->setDictionary(common_dic.get());
+ std::swap(col->getOwnDictionary(), common_dic);
+ }
}
else if (refcol->type() == ibis::UINT) {
col->setDictionary(refcol->getDictionary());
@@ -11484,30 +11499,31 @@ long ibis::bord::column::append(const ibis::column&
scol,
break;}
case ibis::UINT: {
std::unique_ptr< array_t<uint32_t> > vals(scol.selectUInts(msk));
- const ibis::bord::column *bc =
- dynamic_cast<const ibis::bord::column*>(&scol);
if (dic == 0) {
+ const ibis::bord::column *bc =
+ dynamic_cast<const ibis::bord::column*>(&scol);
if (bc != 0)
dic = bc->dic;
- } else if (bc != nullptr && dic != bc->getDictionary()) {
- // the dictionaries are different. merge the source
- // dictionary and remap the source column
+ } else if (dic != scol.getDictionary()) {
+ // remap the source column using the common dictionary
if (this->own_dic.get() == nullptr) {
- this->own_dic.reset(new ibis::dictionary(*dic));
- this->dic = this->own_dic.get();
+ throw "own_dic should not be null";
}
- const ibis::dictionary* sdic = bc->getDictionary();
- this->own_dic->merge(*sdic);
- uint32_t oldToNew[sdic->size()];
- for (uint32_t i = 0; i < sdic->size(); i++) {
+ const ibis::dictionary* sdic = scol.getDictionary();
+ uint32_t oldToNew[sdic->size()+1];
+ for (uint32_t i = 0; i < sdic->size()+1; i++) {
const char* sstr = (*sdic)[i];
oldToNew[i] = (*dic)[sstr];
}
if (vals.get() != nullptr) {
- array_t<uint32_t>* valsp = vals.get();
- for (uint32_t i = 0; i < valsp->size(); i++) {
- (*valsp)[i] = oldToNew[(*valsp)[i]];
- }
+ // cannot remap in place because vals is probably mmapped read
only memory
+ std::unique_ptr<array_t<uint32_t>> remapped(new
ibis::array_t<uint32_t>(vals->size()));
+ std::transform(
+ vals->begin(),
+ vals->end(),
+ remapped->begin(),
+ [&oldToNew](uint32_t x) { return oldToNew[x]; });
+ std::swap(vals, remapped);
}
}
if (vals.get() != 0)
diff --git a/fastbit/fastbit-ibis1.3.5/src/bord.h
b/fastbit/fastbit-ibis1.3.5/src/bord.h
index d6b0f5d..529e7b6 100755
--- a/fastbit/fastbit-ibis1.3.5/src/bord.h
+++ b/fastbit/fastbit-ibis1.3.5/src/bord.h
@@ -612,6 +612,7 @@ public:
virtual const ibis::dictionary* getDictionary() const {return dic;}
/// Assign the dictionary to use.
void setDictionary(const ibis::dictionary* d) {dic = d;}
+ std::unique_ptr<ibis::dictionary>& getOwnDictionary() { return
this->own_dic; }
const ibis::array_t<uint64_t>& getMeshShape() const {return shape;}
int setMeshShape(uint64_t*, uint64_t);
diff --git a/fastbit/fastbit-ibis1.3.5/src/filter.cpp
b/fastbit/fastbit-ibis1.3.5/src/filter.cpp
index b4ee869..c68c742 100755
--- a/fastbit/fastbit-ibis1.3.5/src/filter.cpp
+++ b/fastbit/fastbit-ibis1.3.5/src/filter.cpp
@@ -2115,7 +2115,7 @@ ibis::table* ibis::filter::sift2S(const
ibis::selectClause &tms,
return brd0.release();
}
- std::unique_ptr<ibis::table> brd2(ibis::bord::groupbyc(*(brd0.get()),
tms));
+ std::unique_ptr<ibis::bord> brd2(ibis::bord::groupbyc(*(brd0.get()), tms));
if (ibis::gVerbose > 2 && brd2.get() != 0) {
ibis::util::logger lg;
lg() << mesg << " produced an in-memory data partition with "
@@ -2127,6 +2127,17 @@ ibis::table* ibis::filter::sift2S(const
ibis::selectClause &tms,
brd2->describe(lg());
}
}
+ // move the common dictionaries from brd1 to brd2 so that they
+ // are not deleted when brd1 leaves scope; the caller will need them
+ // to resolve categories ids on the result
+ const ibis::table::stringList& colnames = brd1->columnNames();
+ for (auto it = colnames.begin(); it != colnames.end(); ++it) {
+ ibis::bord::column * col1 =
dynamic_cast<ibis::bord::column*>(brd1->getColumn(*it));
+ ibis::bord::column * col2 =
dynamic_cast<ibis::bord::column*>(brd2->getColumn(*it));
+ if (col1 != nullptr && col2 != nullptr) {
+ std::swap(col1->getOwnDictionary(), col2->getOwnDictionary());
+ }
+ }
return brd2.release();
} // ibis::filter::sift2S
_______________________________________________
FastBit-users mailing list
[email protected]
https://hpcrdm.lbl.gov/cgi-bin/mailman/listinfo/fastbit-users
