#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
