Yes, I did actually run the code before I posted it.
w.r.t. varint encoding. You have two choices w.r.t. a variable length encoded, you could examine the data to accurately predict the output size OR you could just return a constant that represents the worst-case (max) size. For individual fields, it probably doesn't matter what you chose, but for fields that are part of something in a container, you probably want the option of NOT running down the container to size up each element -- so you'd just choose the worst-case size for the estimator.
Though this code doesn't show it, I wrote some pseudo-code in a previous e-mail that glues this framework into the bufferlist stuff. That pseudo code is well prepared for estimate functions that are too large (indeed, it expects that to happen) and it naturally handles buffer overrun detection.
I didn't describe it in the example, but this framework very naturally handles versioning, you just add some code like:
Struct abc {
Int version;
Int a;
Int b;
..... enc_dec(p) {
::enc_dec(p, version);
::enc_dec(p, a);
If (s != DECODE || version > 5) ::enc_dec(p, b); // This field is present in all estimate and encode operations, but only in decode operations when version is > 5
}
};
What this framework doesn't yet handle very well is situations where you have a container with a contained type that is a primitive (i.e., uint8) and you want that contained type to be custom encoded.
Currently, the only solution is replace the contained primitive type with a class wrapper. Unfortunately a typedef is NOT sufficient to differentiate it.
Allen Samuels
SanDisk |a Western Digital brand
2880 Junction Avenue, San Jose, CA 95134
T: +1 408 801 7030| M: +1 408 780 6416
allen.samuels@xxxxxxxxxxx
> -----Original Message-----
> From: Mark Nelson [mailto:mnelson@xxxxxxxxxx]
> Sent: Thursday, July 14, 2016 4:16 AM
> To: Allen Samuels <Allen.Samuels@xxxxxxxxxxx>; Sage Weil
> <sweil@xxxxxxxxxx>
> Cc: ceph-devel <ceph-devel@xxxxxxxxxxxxxxx>
> Subject: Re: bluestore onode diet and encoding overhead
>
> On 07/14/2016 12:52 AM, Allen Samuels wrote:
> > As promised, here's some code that hacks out a new encode/decode
> framework. That has the advantage of only having to list the fields of a struct
> once and is pretty much guaranteed to never overrun a buffer....
> >
> > Comments are requested :)
>
> It compiles! :D
>
> I looked over the code, but I want to look it over again after I've had my
> coffee since I'm still shaking the cobwebs out. Would the idea here be that if
> you are doing varint encoding for example that you always allocate the
> buffer based on ESTIMATE (also taking into account the encoding overhead),
> but typically expect a much smaller encoding?
>
> As it is, it's very clever.
>
> Mark
>
> >
> >
> > #include <iostream>
> > #include <fstream>
> > #include <set>
> > #include <string>
> > #include <string.h>
> >
> > /*******************************************************
> >
> >
> > New fast encode/decode framework.
> >
> > The entire framework is built around the idea that each object has three
> operations:
> >
> > ESTIMATE -- worst-case estimate of the amount of storage required for
> this object
> > ENCODE -- encode object into buffer of size ESTIMATE
> > DECODE -- encode object from buffer of size actual.
> >
> > Each object has a single templated function that actually provides all three
> operations in a single set of code.
> > But doing this, it's pretty much guaranteed that the ESTIMATE and the
> ENCODE code are in harmony (i.e. that the estimate is correct)
> > it also saves a lot of typing/reading...
> >
> > Generally, all three operations are provided on a single function name
> with the input and return parameters overloaded to distinguish them.
> >
> > It's observed that for each of the three operations there is a single value
> which needs to be transmitted between each of the micro-encode/decode
> calls
> > Yes, this is confusing, but let's look at a simple example
> >
> > struct simple {
> > int a;
> > float b;
> > string c;
> > set<int> d;
> > };
> >
> > To encode this struct we generate a function that does the micro-
> encoding of each of the fields of the struct
> > Here's an example of a function that does the ESTIMATE operation.
> >
> > size_t simple::estimate() {
> > return
> > sizeof(a) +
> > sizeof(b) +
> > c.size() +
> > d.size() * sizeof(int);
> > }
> >
> > We're going to re-write it as:
> >
> > size_t simple::estimate(size_t p) {
> > p = estimate(p,a);
> > p = estimate(p,b);
> > p = estimate(p,c);
> > p = estimate(p,d);
> > return p;
> > }
> >
> > assuming that the sorta function:
> >
> > template<typename t> size_t estimate(size_t p,t& o) { return p +
> sizeof(o); }
> > template<typename t> size_t estimate(size_t p,set<t>& o) { return
> > p + o.size() * sizeof(t); }
> >
> >
> > similarly, the encode operation is represented as:
> >
> > char * simple::encode(char *p) {
> > p = encode(p,a);
> > p = encode(p,b);
> > p = encode(p,c);
> > p = encode(p,d);
> > return p;
> > }
> >
> > similarly, the decode operation is represented as:
> >
> > const char * simple::decode(const char *p) {
> > p = decode(p,a);
> > p = decode(p,b);
> > p = decode(p,c);
> > p = decode(p,d);
> > return p;
> > }
> >
> >
> > You can now see that it's possible to create a single function that
> > does all three operations in a single block of code, provided that you can
> fiddle the input/output parameter types appropriately.
> >
> > In essence the pattern is
> >
> > p = enc_dec(p,struct_field_1);
> > p = enc_dec(p,struct_field_2);
> > p = enc_dec(p,struct_field_3);
> >
> > With the type of p being set differently for each operation, i.e.,
> > for ESTIMATE, p = size_t
> > for ENCODE, p = char *
> > for DECODE, p = const char *
> >
> > This is the essence of how the encode/decode framework operates.
> Though there is some more sophistication...
> >
> > ----------------------
> >
> > We also want to allow the encode/decode machinery to be per-type and
> > to operate
> >
> >
> **********************************************************
> ************
> > *******/
> >
> > using namespace std;
> >
> > //
> > // Just like the existing encode/decode machinery. The environment
> > provides a rich set of // pre-defined encodes for primitive types and
> > containers //
> >
> > #define DEFINE_ENC_DEC_RAW(type) \
> > inline size_t enc_dec(size_t p,type &o) { return p + sizeof(type); } \
> > inline char * enc_dec(char *p, type &o) { *(type *)p = o; return p +
> sizeof(type); } \
> > inline const char *enc_dec(const char *p,type &o) { o = *(const type
> > *)p; return p + sizeof(type); }
> >
> > DEFINE_ENC_DEC_RAW(int);
> > DEFINE_ENC_DEC_RAW(size_t);
> >
> > //
> > // String encode/decode (Yea, I know size_t isn't portable -- this is
> > an EXAMPLE man...) // inline size_t enc_dec(size_t p,string& s) {
> > return p + sizeof(size_t) + s.size(); } inline char * enc_dec(char *
> > p,string& s) { *(size_t *)p = s.size();
> > memcpy(p+sizeof(size_t),s.c_str(),s.size()); return p + sizeof(size_t)
> > + s.size(); } inline const char *enc_dec(const char *p,string& s) { s
> > = string(p + sizeof(size_t),*(size_t *)p); return p + sizeof(size_t) +
> > s.size(); }
> >
> > //
> > // Let's do a container.
> > //
> > // One of the problems with a container is that making an accurate
> > estimate of the size // would theoretically require that you walk the entire
> container and add up the sizes of each element.
> > // We probably don't want to do that. So here, I do a hack that just
> > assumes that I can fake up a individual element // and multiple that
> > by the number of elements in a container. This hack works anytime that
> > the estimate function // for the contained type has a fixed maximum size.
> BTW, this is safe, if the contained type has a variable size // (like set<string>)
> then it will fault out the first time you run it.
> > //
> > // Naturally, something like set<string> or map<string,string> is a
> > highly desirable thing to be able to encode/decode // there's no reason
> that you can't create a enc_dec_slow function that properly computes the
> maximum size by walking the container.
> > //
> > template<typename t>
> > inline size_t enc_dec(size_t p,set<t>& s) { return p + sizeof(size_t)
> > + (s.size() * ::enc_dec(size_t(0),*(t *) 0)); }
> >
> > template<typename t>
> > inline char *enc_dec(char *p,set<t>& s) {
> > size_t sz = s.size();
> > p = enc_dec(p,sz);
> > for (const t& e : s) {
> > p = enc_dec(p,const_cast<t&>(e));
> > }
> > return p;
> > }
> >
> > template<typename t>
> > inline const char *enc_dec(const char *p,set<t>&s) {
> > size_t sz;
> > p = enc_dec(p,sz);
> > while (sz--) {
> > t temp;
> > p = enc_dec(p,temp);
> > s.insert(temp);
> > }
> > return p;
> > }
> >
> > //
> > // Specialized encode/decode for a single data type. These are invoked
> explicitly...
> > //
> > inline size_t enc_dec_lba(size_t p,int& lba) {
> > return p + sizeof(lba); // Max....
> > }
> >
> > inline char * enc_dec_lba(char *p,int& lba) {
> > *p = 15;
> > return p + 1; // blah blah
> > }
> >
> > inline const char *enc_dec_lba(const char *p,int& lba) {
> > lba = *p;
> > return p+1;
> > }
> >
> > //
> > // Specialized encode/decode for more sophisticated things primitives.
> > //
> > // Here's an example of a encode/decoder for a pair of fields //
> > inline size_t enc_dec_range(size_t p,short& start,short& end) {
> > return p + 2 * sizeof(short);
> > }
> >
> > inline char *enc_dec_range(char *p, short& start, short& end) {
> > short *s = (short *) p;
> > s[0] = start;
> > s[1] = end;
> > return p + sizeof(short) * 2;
> > }
> >
> > inline const char *enc_dec_range(const char *p,short& start, short& end) {
> > start = *(short *)p;
> > end = *(short *)(p + sizeof(short));
> > return p + 2*sizeof(short);
> > }
> >
> >
> > //
> > // Some C++ template wizardry to make the single encode/decode
> function possible.
> > //
> > enum SERIAL_TYPE {
> > ESTIMATE,
> > ENCODE,
> > DECODE
> > };
> >
> > template <enum SERIAL_TYPE s> struct serial_type;
> >
> > template<> struct serial_type<ESTIMATE> { typedef size_t type; };
> > template<> struct serial_type<ENCODE> { typedef char * type; };
> > template<> struct serial_type<DECODE> { typedef const char *type; };
> >
> > //
> > // This macro is the key, it connects the external non-member function to
> the correct member function.
> > //
> > #define DEFINE_STRUCT_ENC_DEC(s) \
> > inline size_t enc_dec(size_t p, s &o) { return o.enc_dec<ESTIMATE>(p); }
> \
> > inline char * enc_dec(char *p , s &o) { return o.enc_dec<ENCODE>(p); }
> \
> > inline const char *enc_dec(const char *p,s &o) { return
> > o.enc_dec<DECODE>(p); }
> >
> > //
> > // Our example structure
> > //
> > struct astruct {
> > int a;
> > set<int> b;
> > int lba;
> > short start,end;
> >
> > //
> > // <<<<< You need to provide this function just one.
> > //
> > template<enum SERIAL_TYPE s> typename serial_type<s>::type
> enc_dec(typename serial_type<s>::type p) {
> > p = ::enc_dec(p,a);
> > p = ::enc_dec(p,b);
> > p = ::enc_dec_lba(p,lba);
> > p = ::enc_dec_range(p,start,end);
> > return p;
> > }
> > };
> >
> > //
> > // This macro connects the global enc_dec to the member function.
> > // One of these per struct declaration //
> > DEFINE_STRUCT_ENC_DEC(astruct);
> >
> >
> > //
> > // Here's a simple test program. The real encode/decode framework
> > needs to be connected to bufferlist using the pseudo-code // that I
> documented in my previous email.
> > //
> >
> > int main(int argc,char **argv) {
> >
> > astruct a;
> > a.a = 10;
> > a.b.insert(2);
> > a.b.insert(3);
> > a.lba = 12;
> >
> > size_t s = a.enc_dec<ESTIMATE>(size_t(0));
> > cout << "Estimated size is " << s << "\n";
> >
> > char buffer[100];
> >
> > char *end = a.enc_dec<ENCODE>(buffer);
> >
> > cout << "Actual storage was " << end-buffer << "\n";
> >
> > astruct b;
> >
> > (void) b.enc_dec<DECODE>(buffer); // decode it
> >
> > cout << "A.a = " << b.a << "\n";
> > for (auto e : b.b) {
> > cout << " " << e;
> > }
> >
> > cout << "\n";
> >
> > cout << "a.lba = " << b.lba << "\n";
> >
> > return 0;
> > }
> >
> >
> > Allen Samuels
> > SanDisk |a Western Digital brand
> > 2880 Junction Avenue, San Jose, CA 95134
> > T: +1 408 801 7030| M: +1 408 780 6416 allen.samuels@xxxxxxxxxxx
> >
> >
> >> -----Original Message-----
> >> From: Mark Nelson [mailto:mnelson@xxxxxxxxxx]
> >> Sent: Tuesday, July 12, 2016 8:13 PM
> >> To: Sage Weil <sweil@xxxxxxxxxx>; Allen Samuels
> >> <Allen.Samuels@xxxxxxxxxxx>
> >> Cc: ceph-devel <ceph-devel@xxxxxxxxxxxxxxx>
> >> Subject: Re: bluestore onode diet and encoding overhead
> >>
> >>
> >>
> >> On 07/12/2016 08:50 PM, Sage Weil wrote:
> >>> On Tue, 12 Jul 2016, Allen Samuels wrote:
> >>>> Good analysis.
> >>>>
> >>>> My original comments about putting the oNode on a diet included the
> >>>> idea of a "custom" encode/decode path for certain high-usage cases.
> >>>> At the time, Sage resisted going down that path hoping that a more
> >>>> optimized generic case would get the job done. Your analysis shows
> >>>> that while we've achieved significant space reduction this has come
> >>>> at the expense of CPU time -- which dominates small object
> >>>> performance (I suspect that eventually we'd discover that the
> >>>> variable length decode path would be responsible for a substantial
> >>>> read performance degradation also -- which may or may not be part of
> >>>> the read performance drop-off that you're seeing). This isn't a
> surprising
> >> result, though it is unfortunate.
> >>>>
> >>>> I believe we need to revisit the idea of custom encode/decode paths
> >>>> for high-usage cases, only now the gains need to be focused on CPU
> >>>> utilization as well as space efficiency.
> >>>
> >>> I still think we can get most or all of the way there in a generic way
> >>> by revising the way that we interact with bufferlist for encode and
> decode.
> >>> We haven't actually tried to optimize this yet, and the current code
> >>> is pretty horribly inefficient (asserts all over the place, and many
> >>> layers of pointer indirection to do a simple append). I think we need
> >>> to do two
> >>> things:
> >>>
> >>> 1) decode path: optimize the iterator class so that it has a const
> >>> char *current and const char *current_end that point into the current
> >>> buffer::ptr. This way any decode will have a single pointer
> >>> add+comparison to ensure there is enough data to copy before falling
> >>> add+into
> >>> the slow path (partial buffer, move to next buffer, etc.).
> >>>
> >>
> >> I don't have a good sense yet for how much this is hurting us in the read
> >> path. We screwed something up in the last couple of weeks and small
> reads
> >> are quite slow.
> >>
> >>> 2) Having that comparison is still not ideal, but we shoudl consider
> >>> ways to get around that too. For example, if we know that we are
> >>> going to decode N M-byte things, we could do an iterator 'reserve' or
> >>> 'check' that ensures we have a valid pointer for that much and then
> >>> proceed without checks. The interface here would be tricky, though,
> >>> since in the slow case we'll span buffers and need to magically fall
> >>> back to a different decode path (hard to maintain) or do a temporary
> >>> copy (probably faster but we need to ensure the iterator owns it and
> >>> frees is later). I'd say this is step 2 and optional; step 1 will have the most
> >> benefit.
> >>>
> >>> 3) encode path: currently all encode methods take a bufferlist& and
> >>> the bufferlist itself as an append buffer. I think this is flawed and
> >>> limiting. Instead, we should make a new class called
> >>> buffer::list::appender (or similar) and templatize the encode methods
> >>> so they can take a safe_appender (which does bounds checking) or an
> >>> unsafe_appender (which does not). For the latter, the user takes
> >>> responsibility for making sure there is enough space by doing a
> >>> reserve() type call which returns an unsafe_appender, and it's their
> >>> job to make sure they don't shove too much data into it. That should
> >>> make the encode path a memcpy + ptr increment (for savvy/optimized
> >> callers).
> >>
> >> Seems reasonable and similar in performance to what Piotr and I were
> >> discussing this morning. As a very simple test I was thinking of doing a
> quick
> >> size computation and then passing that in to increase the append_buffer
> size
> >> when the bufferlist is created in Bluestore::_txc_write_nodes. His idea
> went
> >> a bit farther to break the encapsulation, compute the fully encoded
> >> message, and dump it directly into a buffer of a computed size without
> the
> >> extra assert checks or bounds checking. Obviously his idea would be
> faster
> >> but more work.
> >>
> >> It sounds like your solution would be similar but a bit more formalized.
> >>
> >>>
> >>> I suggest we use bluestore as a test case to make the interfaces work
> >>> and be fast. If we succeed we can take advantage of it across the
> >>> reset of the code base as well.
> >>
> >> Do we have other places in the code with similar byte append behavior?
> >> That's what's really killing us I think, especially with how small the new
> >> append_buffer is when you run out of space when appending bytes.
> >>
> >>>
> >>> That's my thinking, at least. I haven't had time to prototype it out
> >>> yet, but I think our goal should be to make the encode/decode paths
> >>> capable of being a memcpy + ptr addition in the fast path, and let
> >>> that guide the interface...
> >>>
> >>> sage
> >>> --
> >>> To unsubscribe from this list: send the line "unsubscribe ceph-devel"
> >>> in the body of a message to majordomo@xxxxxxxxxxxxxxx More
> >> majordomo
> >>> info at http://vger.kernel.org/majordomo-info.html
> >>>
--
To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
