|
|
|
|
Sponsored Link •
|
|
Advertisement
|
Don't ever let anyone tell you that STL is nice and abstract and all that, but it just doesn't perform well. I poke holes in that myth in several places in this book (Extended STL, Volume 1: Collections and Iterators, Sections 17.1.1, 19.1.1, 27.9, 36.2.2, and 38.2.1), but this chapter blows it clean out of the water.
The subject matter of this chapter is Scatter/Gather I/O (also known as Scatter I/O), which means the exchange of data between application code and (usually kernel) I/O routines in the form of multiple blocks per action. Its primary intent is to allow client code to manipulate application-level packet headers separately from the payloads, but it can also be turned to other cunning ends, and can yield considerable performance benefits.
The cost is that it complicates the manipulation of data when logically contiguous data is spread over physically discontiguous blocks. To aid in handling such cases, we may use classes that (re)linearize the data back to an acceptably manipulable abstraction.
Since this is a book about extending STL, the abstraction
we will seek is that of an STL collection (Section 2.2) and its
associated iterator ranges. But as we will see, there is a cost in such
abstractions, so we will go further and examine how we might optimize
the transfer of information without diluting the power of the
abstraction. This will lead us into looking into the rules regarding
overriding functions in the std namespace and how we may accommodate one
with the other.
Scatter/Gather I/O involves the exchange of information between an I/O API
and client code in a physically discontiguous form. In all cases I've come
across, this discontiguous form involves a number of separate memory blocks.
For example, the UNIX readv() and writev() functions
act like their read() and write() siblings, but,
rather than a pointer to a single area of memory and its size, they are passed
an array of iovec structures:
struct iovec
{
void* iov_base;
size_t iov_len;
};
ssize_t readv(int fd, const struct iovec* vector, int count);
ssize_t writev(int fd, const struct iovec* vector, int count);
The Windows Sockets API has an analogous structure and corresponding functions:
struct WSABUF
{
u_long len;
char* buf;
};
int WSARecv(SOCKET s
, WSABUF* lpBuffers
, DWORD dwBufferCount
, . . . // And 4 more parameters);
int WSASend(SOCKET s
, WSABUF* lpBuffers
, DWORD dwBufferCount
, . . . // And 4 more parameters);
int WSARecvFrom(SOCKET s
, WSABUF* lpBuffers
, DWORD dwBufferCount
, . . . // And 6 more parameters);
int WSASendTo( SOCKET s
, WSABUF* lpBuffers
, DWORD dwBufferCount
, . . . // And 6 more parameters);
You might wonder why people would want to perform I/O in such a fashion, given the obvious complication to client code. Well, if your file or network data has a fixed format, you can read one or more records/packets in or out without any need to move, reformat, or coalesce them. This can be quite a convenience. Similarly, if your records/packets have variable format but a fixed-size header, you can read/write the header directly to/from a matching structure and treat the rest as an opaque variable-size blob. And there's a third reason: performance. I once created a network server architecture using Scatter/Gather I/O that used a multithreaded nonlocking memory allocation scheme. (Suffice to say, it was rather nippy.)
But however much Scatter/Gather I/O may help in terms of performance, when dealing with variable-length records/packets, or those whose payloads contain elements that are variable-length, the client code is complicated, usually low on transparency, and bug-prone. An efficient abstraction is needed.
The challenge with Scatter/Gather I/O is that using memory scattered over multiple blocks is not a trivial matter. On projects (on Windows platforms) in the 1990s, I tended to use a custom COM stream implementation from my company's proprietary libraries, which was implemented for a different task some years previously. Permit me to talk about the COM stream architecture for a moment. (I know I promised in the last chapter there would be no more COM, but there is a point to this, even for UNIX diehards. Trust me, I'm a doctor!)
A COM stream is an abstraction over an underlying storage medium having
much in common with the file abstractions we're used to. Essentially, it
has access to the underlying medium and defines a current point within
its logical extent. A stream object exhibits the IStream interface
(shown in abbreviated form in Listing 31.1), which contains a number of
methods, including Seek(), SetSize(), Stat(),
and Clone().
There are also methods for acquiring exclusive access to regions of the
underlying medium. The IStream interface derives from
ISequentialStream (also shown in Listing 31.1), which defines the
two methods Read() and Write().You can implement a
stream for a particular underlying medium directly by deriving from IStream and
providing suitable definitions for its methods.
Listing 31.1 Definition of the ISequentialStream and IStream Interfaces
interface ISequentialStream
: public IUnknown
{
virtual HRESULT Read(void* p, ULONG n, ULONG* numRead) = 0;
virtual HRESULT Write(void const* p, ULONG n, ULONG* numWritten) = 0;
};
interface IStream
: public ISequentialStream
{
virtual HRESULT Seek(. . .) = 0;
virtual HRESULT SetSize(. . .) = 0;
virtual HRESULT CopyTo(. . .) = 0;
virtual HRESULT Commit(. . .) = 0;
virtual HRESULT Revert(. . .) = 0;
virtual HRESULT LockRegion(. . .) = 0;
virtual HRESULT UnlockRegion(. . .) = 0;
virtual HRESULT Stat(. . .) = 0;
virtual HRESULT Clone(. . .) = 0;
};
COM defines another stream-related abstraction, in the form of the
ILockBytes interface (shown in abbreviated form in Listing 31.2). It
abstracts arbitrary underlying mediums as a logically contiguous array
of bytes. It does not maintain any positional state. Hence, it has
ReadAt() and WriteAt() methods rather than Read() and Write().
Listing 31.2 Definition of the ILockBytes Interface
interface ILockBytes
: public IUnknown
{
virtual HRESULT ReadAt( ULARGE_INTEGER pos, void* p
, ULONG n, ULONG* numRead) = 0;
virtual HRESULT WriteAt(ULARGE_INTEGER pos, void const* p
, ULONG n, ULONG* numWritten) = 0;
virtual HRESULT Flush() = 0;
virtual HRESULT SetSize(. . .) = 0;
virtual HRESULT LockRegion(. . .) = 0;
virtual HRESULT UnlockRegion(. . .) = 0;
virtual HRESULT Stat(. . .) = 0;
};
It is a relatively simple matter to implement a COM stream in terms
of (an object that exhibits) the ILockBytes interface. All that's
required is an ILockBytes* and a position. My company has just such an
entity, accessible via the CreateStreamOnLockBytes() function:
HRESULT CreateStreamOnLockBytes(ILockBytes* plb, unsigned flags
, IStream** ppstm);
Obviously, the next question is, "How do we get hold of an ILockBytes
object?" Again, there's a function for that, CreateLockBytesOnMemory():
HRESULT CreateLockBytesOnMemory(void* pv
, size_t si
, unsigned flags
, void* arena
, ILockBytes** pplb);
This supports a whole host of memory scenarios, including using a fixed
buffer, using Windows "global" memory, using a COM allocator
(IAllocator), and so on. One of the many flags is SYCLBOMF_FIXED_ARRAY,
which indicates that pv points to an array of MemLockBytesBlock
structures:
struct MemLockBytesBlock
{
size_t cb;
void* pv;
};
I'm not going to bang on about this much more, as hindsight is a harsh
judge of things such as opaque pointers whose meanings are moderated by
flags. The point I want to get across about this stuff is that I was
able to take a set of memory blocks containing the scattered packet
contents and get back an IStream pointer from which the packet
information can be extracted in a logical and linear manner. Such code
takes the following simple and reasonably transparent form. (Error
handling is elided for brevity.) The ref_ptr instances are used to
ensure that the reference counts are managed irrespective of any early
returns and/or exceptions.
std::vector<WSABUF> blocks = . . .
size_t payloadSize = . . .
ILockBytes* plb;
IStream* pstm;
SynesisCom::CreateLockBytesOnMemory(&blocks[1], payloadSize
, SYCLBOMF_FIXED_ARRAY | . . ., NULL, &plb);
stlsoft::ref_ptr<ILockBytes> lb(pbl, false); // false "eats" the ref
SynesisCom::CreateStreamOnLockBytes(plb, 0, &pstm);
stlsoft::ref_ptr<IStream> stm(pstm, false); // false "eats" the ref
. . . // Pass off stm to higher-layer processing
The stream can then be wrapped by a byte-order-aware Instance Adaptor class that works in partnership with a message object Factory, to complete the mechanism for efficient translation from TCP packet stream segments to instances of higher-level protocol (C++) objects. The high efficiencies obtainable by such a scheme result from there being no allocations of, and no copying into, memory that does not constitute part of the final translated message object instances.
This is a powerful basis for a communications server model, one that I've used several times, albeit in different guises. In the case described earlier, a number of characteristics of the approach might incline you to search, as I have done, for better, less technology-specific solutions.
First, the major downside of the described mechanism is that, being COM, the server code is effectively Windows-specific. Second, many developers (incorrectly) consider COM, as they (equally incorrectly) do C++ and STL, to be intrinsically inefficient, and it can be hard to disabuse them of that notion even with hard facts. Finally, add in the type-unsafe opaque pointers and the fact that the stream and lock-bytes classes were hidden proprietary implementations, and it all leaves something to be desired.
platformstl::scatter_slice_sequence—A Teaser TrailerAn alternate representation is to be found in a new, and still
evolving, component in the PlatformSTL subproject:
scatter_slice_sequence. This Facade class template maintains an array of
slice structures describing a set of I/O buffers and provides methods
for invoking native read/write functions on the set of buffers, in
addition to providing STL collection access (in the form of begin() and
end() methods). The class works with both iovec and WSABUF by
abstracting their features with attribute shims (Section 9.2.1)
get_scatter_slice_size, get_scatter_slice_ptr, and
get_scatter_slice_size_member_ptr, shown in Listing 31.3.
Listing 31.3 Attribute Shims for the iovec and WSABUF Structures
#if defined(PLATFORMSTL_OS_IS_UNIX)
inline void* const get_scatter_slice_ptr(struct iovec const& ss)
{
return ss.iov_base;
}
inline void*& get_scatter_slice_ptr(struct iovec& ss);
inline size_t get_scatter_slice_size(struct iovec const& ss)
{
return static_cast<size_t>(ss.iov_len);
}
inline size_t& get_scatter_slice_size(struct iovec& ss);
inline size_t iovec::*
get_scatter_slice_size_member_ptr(struct iovec const*)
{
return &iovec::iov_len;
}
#elif defined(PLATFORMSTL_OS_IS_WIN32)
inline void const* get_scatter_slice_ptr(WSABUF const& ss)
{
return ss.buf;
}
inline void*& get_scatter_slice_ptr(WSABUF& ss);
inline size_t get_scatter_slice_size(WSABUF const& ss)
{
return static_cast<size_t>(ss.len);
}
inline size_t& get_scatter_slice_size(WSABUF& ss);
inline u_long WSABUF::* get_scatter_slice_size_member_ptr(WSABUF const*)
{
return &WSABUF::len;
}
#endif /* operating system */
scatter_slice_sequence currently provides for
readv()/ writev() on UNIX and
WSARecv()/WSASend() and
WSARecvFrom()/WSASendTo() on Windows. Listing 31.4 shows an
example that uses an iovec specialization of the class template to read the
contents from one file descriptor into a number of buffers, processes the
content in an STL kind of way, and then writes the converted contents to
another file descriptor.
Listing 31.4 Example Use of scatter_slice_sequence with
readv() and writev()
int fs = . . . // Opened for read
int fd = . . . // Opened for write
for(;;)
{
const size_t BUFF_SIZE = 100;
const size_t MAX_BUFFS = 10;
char buffers[MAX_BUFFS][BUFF_SIZE];
const size_t numBuffers = rand() % MAX_BUFFS;
// Declare an instance with arity of numBuffers
platformstl::scatter_slice_sequence<iovec> sss(numBuffers);
// Set up each slice in the sequence, which may be of
// different sizes in reality
{ for(size_t i = 0; i < numBuffers; ++i)
{
sss.set_slice(i, &buffers[i][0], sizeof(buffers[i]));
}}
if(0 != numBuffers) // In real scenario, might get 0 buffers
{
size_t n = sss.read(::readv, fs); // Read from fs using ::readv()
if(0 == n)
{
break;
}
// "Process" the contents
std::transform( sss.payload().begin(), sss.payload().begin() + n
, sss.payload().begin(), ::toupper);
sss.write(::writev, fd, n); // Write n to fd using ::writev()
}
}
Obviously this example is very stripped down, but I trust your abilities to
imagine that fs and fd might represent sockets, that
the buffers shown here would be obtained from a shared memory arena (which may
not have any to spare at a given time), and that the "processing" would be
something less trivial than setting the contents to uppercase before
(re)transmission.
The sequence's payload (available via payload()) provides random
access iterators over the contents of its memory blocks. Just as with
std::deque, it's important to realize that these iterators are not
contiguous (Section 2.3.6)! Pointer arithmetic on the iterators is a
constant-time operation, but iterating the range is not a linear-time
operation. The scatter_slice_sequence is still a work in progress, and
its interface might evolve further before it's released into the
PlatformSTL subproject proper. (It is on the CD.) But what it clearly
provides is the ability to represent a given set of data blocks as an
STL sequence (Section 2.2), along with adaptor methods read() and
write() that take a file/socket handle and a Scatter/Gather I/O function
and apply them to the blocks. This is the logical equivalent of the COM
stream object created via CreateLockBytesOnMemory() +
SYCLBOMF_FIXED_ARRAY and CreateStreamOnLockBytes(). The one apparent
disadvantage is that its contents have to be traversed one element at a
time, something that may have performance costs. (Hint: This is a clue
about something interesting to follow. . . .)
Adapting ACE_Message_QueueThe main subject of this chapter covers my efforts to adapt the
memory queues of the Adaptive Communications Environment (ACE) to the
STL collection concept, to serve the requirements of one of my recent
commercial networking projects, a middleware routing service. To use the
ACE Reactor framework, you derive event handler classes from
ACE_Event_Handler (overriding the requisite I/O event handler methods)
and register instances of them with the program's reactor singleton.
When the reactor encounters an I/O event of a type for which an instance
is registered, it invokes the appropriate callback method on the
handler. When used with TCP, the Internet's stream-oriented transport
protocol, the common idiom is to handle received data into instances of
ACE_Message_Block and queue them in an instance of (a specialization of)
the class template ACE_Message_Queue, as shown (with error handling
omitted for brevity) in Listing 31.5.
Listing 31.5 A Simple Event Handler for the ACE Reactor Framework
class SimpleTCPReceiver
: public ACE_Event_Handler
{
. . .
virtual int handle_input(ACE_HANDLE h)
{
const size_t BLOCK_SIZE = 1024;
ACE_Message_Block* mb = new ACE_Message_Block(BLOCK_SIZE);
ssize_t n = m_peer.recv(mb->base(), mb->size());
mb->wr_ptr(n);
m_mq.enqueue_tail(mb);
return 0;
}
. . .
private: // Member Variables
ACE_SOCK_Stream m_peer; // Connection socket
ACE_Message_Queue<ACE_SYNCH_USE> m_mq; // Message queue
};
The ACE_Message_Queue class acts as an ordered repository for all
blocks, thereby faithfully representing the data stream. But
ACE_Message_Queue is strictly a container of blocks; it does not attempt
to provide any kind of abstracted access to the contents of the blocks.
To access the contents of a message queue, you can use the associated
class template, ACE_Message_Queue_Iterator, to iterate the blocks, as
shown in Listing 31.6. The ACE_Message_Queue_Iterator::next() method
returns a nonzero result and sets the given pointer reference to the
block if a next block is available; otherwise, it returns 0. The
advance() method moves the current enumeration point to the next block
(if any).
Listing 31.6 Example Code That Uses ACE_Message_Queue_Iterator
void SimpleTCPReceiver::ProcessQueue()
{
ACE_Message_Queue_Iterator<ACE_NULL_SYNCH> mqi(m_mq);
ACE_Message_Block* mb;
for(; mqi.next(mb); mqi.advance())
{
{ for(size_t i = 0; i < mb->length(); ++i)
{
printf("%c", i[mb->rd_ptr()];
}}
mb->rd_ptr(mb->length()); // Advance read ptr to "exhaust" block
}
}
Obviously, if you want to process a set of blocks as a logically contiguous single block, it's going to be a bit messy. We need a sequence to flatten the stream for STL manipulation.
acestl::message_queue_sequence, Version 1The ACESTL subproject contains a number of components for adapting ACE
to STL (and for making ACE components easier to use).
acestl::message_queue_sequence is a class template that acts as an
Instance Adaptor for the ACE_Message_Queue. Since this component's got
quite a kick, I'm going to play my usual author's dirty trick of
presenting you with a progression of implementations. Thankfully, unlike
some material covered in other chapters, the changes between the
versions are entirely additive, which should help keep me under 40 pages
for this topic. Listing 31.7 shows the definition of the first version.
Listing 31.7 Definition of message_queue_sequence
// In namespace acestl
template <ACE_SYNCH_DECL>
class message_queue_sequence
{
public: // Member Types
typedef char value_type;
typedef ACE_Message_Queue<ACE_SYNCH_USE> sequence_type;
typedef message_queue_sequence<ACE_SYNCH_USE> class_type;
typedef size_t size_type;
class iterator;
public: // Construction
explicit message_queue_sequence(sequence_type> mq);
public: // Iteration
iterator begin();
iterator end();
public: // Attributes
size_type size() const;
bool empty() const;
private: // Member Variables
sequence_type& m_mq;
private: // Not to be implemented
message_queue_sequence(class_type const&);
class_type& operator =(class_type const&);
};
Given what we've seen with previous sequences, there's little here that
needs to be remarked on; the interesting stuff will be in the iterator class.
Note that the value type is char, meaning that size() returns the
number of bytes in the queue, and [begin(), end())
defines the range of bytes. No methods pertain to message blocks.
31.4.2 acestl::message_queue_sequence::iterator
Listing 31.8 shows the definition of the
acestl::message_queue_sequence::iterator class. Again, a lot here should
be familiar based on prior experience. (I hope by now you're building a
familiarity with these techniques, recognizing their similarities and
identifying the differences between the different cases of their
application. Naturally, it's my hope that this stands you in great stead
for writing your own STL extensions.)
The iterator category is input
iterator (Section 1.3.1). The element reference category (Section 3.3)
is transient or higher; in fact, it's fixed, with the caveat that no
other code, within or without the defining thread, changes the contents
of the underlying message queue or its blocks (in which case it would be
invalidatable). The iterator is implemented in terms of a shared_handle,
discussed shortly. I've not shown the canonical manipulation of the
shared_handle in the construction methods since we've seen it before in
other sequences (Sections 19.3 and 20.5).
Listing 31.8 Definition of message_queue_sequence::iterator
class message_queue_sequence<. . .>::iterator
: public std::iterator>std::input_iterator_tag
, char, ptrdiff_t
, char*, char&
>
{
private: // Member Types
friend class message_queue_sequence<ACE_SYNCH_USE>;
typedef ACE_Message_Queue_Iterator<ACE_SYNCH_USE> mq_iterator_type;
struct shared_handle;
public:
typedef iterator class_type;
typedef char value_type;
private: // Construction
iterator(sequence_type& mq)
: m_handle(new shared_handle(mq))
{}
public:
iterator()
: m_handle(NULL)
{}
iterator(class_type const& rhs); // Share handle via AddRef() (+)
~iterator() throw(); // Call Release() (-) if non-NULL
class_type& operator =(class_type const& rhs); // (+) new; (-) old
public: // Input Iteration
class_type& operator ++()
{
ACESTL_ASSERT(NULL != m_handle);
if(!m_handle->advance())
{
m_handle->Release();
m_handle = NULL;
}
return *this;
}
class_type operator ++(int); // Canonical implementation
value_type& operator *()
{
ACESTL_ASSERT(NULL != m_handle);
return m_handle->current();
}
value_type operator *() const
{
ACESTL_ASSERT(NULL != m_handle);
return m_handle->current();
}
bool equal(class_type const& rhs) const
{
return lhs.is_end_point() == rhs.is_end_point();
}
private: // Implementation
bool is_end_point() const
{
return NULL == m_handle || m_handle->is_end_point();
}
private: // Member Variables
shared_handle* m_handle;
};
The iteration methods are implemented in terms of the methods of
shared_handle. The endpoint state is identified by either a NULL handle
or a handle that identifies itself as being at the endpoint. The
preincrement operator advances by calling shared_handle::advance() and
releases the handle when advance() returns false. The dereference
operator overloads are implemented in terms of the current() overloads
of shared_handle. Note that the mutating (non-const) overload returns a
mutating reference, whereas the nonmutating (const) overload returns a
char by value.
The main action lies in the shared_handle. Listing 31.9 shows its
implementation. I'm going to invoke another low author tactic now and not
explain the fine detail of the algorithm. I'll leave it as an exercise for you
to figure out. To be fair, though, I will note that it skips empty
ACE_Message_Block instances, which is how its endpoint condition can be so
simple.
Listing 31.9 Definition of shared_handle
struct message_queue_sequence<. . .>::iterator::shared_handle
{
public: // Member Types
typedef shared_handle class_type;
public: // Member Variables
mq_iterator_type m_mqi;
ACE_Message_Block* m_entry;
size_t m_entryLength;
size_t m_entryIndex;
private:
sint32_t m_refCount;
public: // Construction
explicit shared_handle(sequence_type& mq)
: m_mqi(mq)
, m_entry(NULL)
, m_entryLength(0)
, m_entryIndex(0)
, m_refCount(1)
{
if(m_mqi.next(m_entry))
{
for(;;)
{
if(0 != (m_entryLength = m_entry->length()))
{
break;
}
else if(NULL == (m_entry = nextEntry()))
{
break;
}
}
}
}
private:
~shared_handle() throw()
{
ACESTL_MESSAGE_ASSERT("Shared handle destroyed with outstanding references!", 0 == m_refCount);
}
public:
sint32_t AddRef(); // Canonical implementation
sint32_t Release(); // Canonical implementation
public: // Iteration Methods
bool is_end_point() const
{
return m_entryIndex == m_entryLength;
}
char& current()
{
ACESTL_ASSERT(NULL != m_entry);
ACESTL_ASSERT(m_entryIndex != m_entryLength);
return m_entryIndex[m_entry->rd_ptr()];
}
char current() const
{
ACESTL_ASSERT(NULL != m_entry);
ACESTL_ASSERT(m_entryIndex != m_entryLength);
return m_entryIndex[m_entry->rd_ptr()];
}
bool advance()
{
ACESTL_MESSAGE_ASSERT("Invalid index", m_entryIndex < m_entryLength);
if(++m_entryIndex == m_entryLength)
{
m_entryIndex = 0;
for(;;)
{
if(NULL == (m_entry = nextEntry()))
{
return false;
}
else if(0 != (m_entryLength = m_entry->length()))
{
break;
}
}
}
return true;
}
private: // Implementation
ACE_Message_Block* nextEntry()
{
ACE_Message_Block* entry = NULL;
return m_mqi.advance() ? (m_mqi.next(entry), entry) : NULL;
}
private: // Not to be implemented
shared_handle(class_type const&);
class_type& operator =(class_type const&);
};
I hope you'll agree that being able to treat a set of
ACE_Message_Block communications stream fragments as a logically
contiguous stream eases considerably the task of dealing with such
streams. In our middleware project, this enabled us to unmarshal the
high-level protocol messages as objects, by the combination of another
Instance Adaptor and a message Factory.
Permit me a small digression about the protocol. Standards Australia defines a protocol for the exchange of electronic payment implementation, called AS2805. This is a very flexible protocol, with a significant drawback. The messages do not contain any message-size information in their fixed format header, and each message can contain a variable number of fields, some of which are of variable size. This means that you can't know whether all of a message has been received from the peer until the message has been fully parsed. Consequently, being able to easily and efficiently deconstruct a message is critical.
This was achieved by applying another Instance Adaptor to the
acestl::message_queue_sequence instance to make it be treated as a
streamable object, similar to how the logically contiguous ILockBytes
instance was turned into a streamable object with
CreateStreamFromLockBytes(). The streamable object is used by the
message Factory, which understands how to read the message type from the
packet header and then uses that type to dispatch the appropriate
unmarshaling function to read the remainder of the message contents and
create a corresponding message instance. If insufficient data is
available, the Factory invocation fails benignly, and the queue contents
remain unchanged until the next I/O event. Only when a full message is
retrieved is the requisite portion of the head of the queue removed and
released back to the memory cache. If the message parsing fails for bad
contents, the peer has sent bad data, and the connection is torn down.
So, we've got some nice abstractions going—some of which have seen
service in large-scale deployments, which is never to be sniffed at—but
you may have been receiving portents from your skeptical
subconsciousness. We're manipulating a number of blocks of contiguous
memory, but the nature of the acestl::message_queue_sequence::iterator
means that each byte in those blocks must be processed one at a time.
This has to have an efficiency cost. And it does.
Before we proceed, I want to trot out the received wisdom on performance,
namely, to avoid premature optimization. More precisely, although it's
something of a simplification, you've usually got only one bottleneck in a
system at a time. Inefficiencies usually make themselves felt only when a
greater inefficiency has been resolved. In none of the applications in which
I've used message_queue_sequence has it been associated with the bottleneck.
However, I tend to be a little efficiency obsessed—What's that? You've
noticed?—and since STLSoft is an open-source publicly available library, the
message_queue_sequence component might find itself being a bottleneck in
someone else's project, and that would never do. So, I want to show you how to
have your cake and eat it too, that is, how to linearize data block contents in
an STL sequence and yet have block-like efficiency.
acestl::message_queue_sequence, Version 2 First, we need to identify when a block transfer is valid. The ACE
libraries define opaque memory in terms of char, that is, the pointers are
either char const* or char*, presumably to make pointer arithmetic
straightforward. I don't hold with this strategy, but that's irrelevant; it is
what it is. When transferring contents between STL iterators of type char* or
char const* and acestl::message_queue_sequence::iterator, we want the
sequence's contents to be block transferred. In other words, the following code
should result in 2 calls to memcpy(), rather than 120 calls to
shared_handle::advance():
ACE_Message_Queue<ACE_NULL_SYNCH> mq; // 2 message blocks, 120 bytes char results[120]; acestl::message_queue_sequence<ACE_NULL_SYNCH> mqs(mq); std::copy(mqs.begin(), mqs.end(), &results[120]);
We want the same efficiency when transferring from contiguous memory into the message queue sequence, as in the following:
std::copy(&results[0], &results[0] + STLSOFT_NUM_ELEMENTS(results)
, mqs.begin());
The first thing we need for this is to define block copy operations for
message_queue_sequence. Listing 31.10 shows the definition of two new
static methods for the sequence class, overloads named fast_copy().
Listing 31.10 Definition of the message_queue_sequence Algorithm Worker Methods
template <ACE_SYNCH_DECL>
class message_queue_sequence
{
. . .
static char* fast_copy(iterator from, iterator to, char* o)
{
#if defined(ACESTL_MQS_NO_FAST_COPY_TO)
for(; from != to; ++from, ++o)
{
*o = *from;
}
#else /* ? ACESTL_MQS_NO_FAST_COPY_TO */
from.fast_copy(to, o);
#endif /* ACESTL_MQS_NO_FAST_COPY_TO */
return o;
}
static iterator fast_copy(char const* from, char const* to
, iterator o)
{
#if defined(ACESTL_MQS_NO_FAST_COPY_FROM)
for(;from != to; ++from, ++o)
{
*o = *from;
}
#else /* ? ACESTL_MQS_NO_FAST_COPY_FROM */
o.fast_copy(from, to);
#endif /* ACESTL_MQS_NO_FAST_COPY_FROM */
return o;
}
. . .
I've deliberately left in the #defines that suppress the block operations,
just to illustrate in code what the alternative, default, behavior is. These
#defines also facilitate tests with and without block copying enabled. (Anyone
sniff a performance test in the near future?) The block mode code uses new
iterator::fast_copy() methods, shown in Listing 31.11.
Listing 31.11 Definition of the iterator Algorithm Worker Methods
class message_queue_sequence<. . .>::iterator
{
. . .
void fast_copy(char const* from, char const* to)
{
if(from != to)
{
ACESTL_ASSERT(NULL != m_handle);
m_handle->fast_copy(from, to, static_cast<size_type>(to - from));
}
}
void fast_copy(class_type const& to, char* o)
{
if(*this != to)
{
ACESTL_ASSERT(NULL != m_handle);
m_handle->fast_copy(to.m_handle, o);
}
}
Tantalizingly, these do very little beyond invoking the same-named new
methods of the shared_handle class, shown in Listing 31.12. For both in and out
transfers, these methods calculate the appropriate portion of each block to be
read/written and effect the transfer with memcpy().
Listing 31.12 Definition of the shared_handle Algorithm Worker Methods
struct message_queue_sequence<. . .>::iterator::shared_handle
{
. . .
void fast_copy(char const* from, char const* to, size_type n)
{
ACESTL_ASSERT(0 != n);
ACESTL_ASSERT(from != to);
if(0 != n)
{
size_type n1 = m_entryLength - m_entryIndex;
if(n <= n1)
{
::memcpy(&m_entryIndex[m_entry->rd_ptr()], from, n);
}
else
{
::memcpy(&m_entryIndex[m_entry->rd_ptr()], from, n1);
from += n1;
m_entry = nextEntry();
ACESTL_ASSERT(NULL != m_entry);
fast_copy(from, to, n - n1);
}
}
}
void fast_copy(class_type const* to, char* o)
{
size_type n1 = m_entryLength - m_entryIndex;
if( NULL != to &&
m_entry == to ->m_entry)
{
::memcpy(o, &m_entryIndex[m_entry->rd_ptr()], n1);
}
else
{
::memcpy(o, &m_entryIndex[m_entry->rd_ptr()], n1);
o += n1;
m_entry = nextEntry();
if(NULL != m_entry)
{
fast_copy(to, o);
}
}
}
. . .
So far so good, but no one wants to write client code such as the following:
ACE_Message_Queue<ACE_NULL_SYNCH> mq; // 2 locks; total 120 bytes
char results[120];
acestl::message_queue_sequence<ACE_NULL_SYNCH> mqs(mq);
acestl::message_queue_sequence<ACE_NULL_SYNCH>::fast_copy(mqs.begin()
, mqs.end(), &results[120]);
We want the invocation std::copy() to pick up our fast version
automatically when the other iterator type is char (const)*. For this we need
to specialize std::copy().
For a number of reasons, defining partial template specializations in the
std namespace is prohibited. This proves inconvenient in two ways. First, and
most importantly, because message_queue_sequence is a template, we want to
cater to all its specializations and so would want to do something like that
shown in Listing 31.13. (For brevity I'm omitting the namespace qualification
acestl from each message_queue_sequence<S>::iterator shown in this
listing and the next.)
Listing 31.13 Illegal Specializations of std::copy()
// In namespace std
template <typename S>
char* copy( typename message_queue_sequence<S>::iterator from
, typename message_queue_sequence<S>::iterator to, char* o)
{
return message_queue_sequence<S>::fast_copy(from, to, o);
}
template <typename S>
typename message_queue_sequence<S>::iterator copy(char* from, char* to
, typename message_queue_sequence<S>::iterator o)
{
return message_queue_sequence<S>::fast_copy(from, to, o);
}
Since we may not do this, we are forced to anticipate the
specializations of message_queue_sequence and (fully) specialize
std::copy() accordingly, as in Listing 31.14. Note that separate char*
and char const* specializations are required for the
char-pointer-to-iterator block transfer, to ensure that copying from
char* and char const* uses the optimization.
Listing 31.14 Legal Specializations of std::copy()
// In namespace std
template <>
char*
copy( typename message_queue_sequence<ACE_NULL_SYNCH>::iterator from
, typename message_queue_sequence<ACE_NULL_SYNCH>::iterator to
, char* o)
{
return message_queue_sequence<ACE_NULL_SYNCH>::fast_copy(from, to, o);
}
. . . // Same as above, but for ACE_MT_SYNCH
template <>
typename message_queue_sequence<ACE_NULL_SYNCH>::iterator
copy(char* from
, char* to
, typename message_queue_sequence<ACE_NULL_SYNCH>::iterator o)
{
return message_queue_sequence<ACE_NULL_SYNCH>::fast_copy(from, to, o);
}
. . . // Same as above, but for ACE_MT_SYNCH
template <>
typename message_queue_sequence<ACE_NULL_SYNCH>::iterator
copy(char const* from
, char const* to
, typename message_queue_sequence<ACE_NULL_SYNCH>::iterator o)
{
return message_queue_sequence<ACE_NULL_SYNCH>::fast_copy(from, to, o);
}
. . . // Same as above, but for ACE_MT_SYNCH
Fortunately, ACE offers only two specializations, in the form of
ACE_NULL_SYNCH (a #define for
ACE_Null_Mutex, ACE_Null_Condition) and
ACE_MT_SYNCH (a #define for
ACE_Thread_Mutex, ACE_Condition_Thread_Mutex),
yielding only six specializations.
But there's more. If, like me, you avoid like the plague the use of
char as a substitute for C++'s missing byte type, you probably
instead use signed char or unsigned
char, both of which are distinct types from char when it comes to
overload resolution (and template resolution). Passing these to an invocation
of std::copy() will not succeed in invoking the optimized transfer
methods. So, with heads bowed low, we need to provide another six
specializations for signed char and six for unsigned char, yielding a total of
eighteen specializations, for what we'd like to have been two, or at most
three, were we able to partially specialize in the std namespace.
Thankfully, all this effort is worth the payoff. Before we look at
that, I just want to answer one question you might be pondering: Why
only std::copy()? In principle there is no reason to not specialize all
possible standard algorithms. The reason I've not done so is twofold.
First, the sheer effort in doing so would be onerous, to say the least;
to avoid a lot of manual plugging around we'd be pragmatically bound to
use macros, and who likes macros? The second reason is more, well,
reasoned. The whole reason for this optimization is to facilitate
high-speed interpretation of data in its original memory block and
high-speed exchange of data into new storage. In my experience, both of
these involve std::copy(). I should admit one exception to this in our
middleware project that required copy_n(). The copy_n() algorithm was
overlooked for incorporation into the C++-98 standard (but will be
included in the next version) and so appears in STLSoft. There are
specializations of it, this time in the stlsoft namespace, in the same
fashion as for std::copy(). Hence, there are a total of 36 function
specializations in the <acestl/collections/message_queue_sequence.hpp>
header file.
Now that we've examined the optimization mechanism, we'd better make
sure it's worth the not inconsiderable effort. In order to demonstrate
the differences in performance between the optimized block copying
version and the original version, I used a test program that creates an
ACE_Message_Queue instance to which it adds a number of blocks, copies
the contents from a char array using std::copy(),copies them back to
another char array (again with std::copy()), and verifies that the
contents of the two arrays are identical. The number of blocks ranged
from 1 to 10. The block size ranged from 10 to 10,000. The times for
copying from the source char array to the sequence, and from the
sequence to the destination char array, were taken separately, using the
PlatformSTL component performance_counter. Each copying operation was
repeated 20,000 times, in order to obtain measurement resolution in
milliseconds. The code is shown in the extra material for this chapter
on the CD.
Table 31.1 shows a representative sample of the results, expressed as percentages of the time (in milliseconds) taken by the equivalent nonoptimized version. As we might expect, with the very small block size of 10, the difference is negligible. For a buffer size of 100, there's an advantage with the optimized form, but it's not stunning. However, when we get to the more realistic buffer sizes of 1,000 and 10,000, there's no competition-the optimized form is 40-50 times faster.
| Array to Iterator | Iterator to Array | ||||||
|---|---|---|---|---|---|---|---|
| Number of Blocks | Block Size | Nonoptimized | Block | % | Nonoptimized | Block | % |
| 1 | 10 | 7 | 6 | 85.7% | 7 | 9 | 128.6% |
| 2 | 10 | 9 | 8 | 88.9% | 9 | 7 | 77.8% |
| 5 | 10 | 16 | 10 | 62.5% | 16 | 10 | 62.5% |
| 10 | 10 | 27 | 14 | 51.9% | 26 | 14 | 53.8% |
| 1 | 100 | 25 | 7 | 28.0% | 23 | 7 | 30.4% |
| 2 | 100 | 46 | 9 | 19.6% | 42 | 9 | 21.4% |
| 5 | 100 | 108 | 14 | 13.0% | 99 | 14 | 14.1% |
| 10 | 100 | 211 | 23 | 10.9% | 188 | 23 | 12.2% |
| 1 | 1,000 | 207 | 10 | 4.8% | 184 | 11 | 6.0% |
| 2 | 1,000 | 416 | 16 | 3.8% | 391 | 17 | 4.3% |
| 5 | 1,000 | 1,025 | 32 | 3.1% | 898 | 32 | 3.6% |
| 10 | 1,000 | 2,042 | 60 | 2.9% | 1,793 | 61 | 3.4% |
| 1 | 10,000 | 2,038 | 29 | 1.4% | 1,786 | 29 | 1.6% |
| 2 | 10,000 | 4,100 | 101 | 2.5% | 3,570 | 101 | 2.8% |
| 5 | 10,000 | 4,143 | 109 | 2.6% | 3,606 | 101 | 2.8% |
| 10 | 10,000 | 4,103 | 102 | 2.5% | 3,573 | 102 | 2.9% |
This chapter has looked at the features of Scatter/Gather I/O, whose APIs
present considerable challenges to STL adaptation. We've examined an
adaptation, in the form of the scatter_slice_sequence component, and have seen
that such sequences must have genuinely random access iterators (i.e., not
contiguous iterators), for which the identity &*it + 2 == &*(it + 2) does not
hold (see Section 2.3.6). Notwithstanding, we've seen how we can take advantage
of their partial contiguity in order to effect significant performance
improvements, something that is particularly important given their use in file
and/or socket I/O. With minimal sacrifice of the Principle of Transparency,
we've made big gains in the Principle of Composition (and also served the
Principle of Diversity along the way).
Have an opinion about scatter/gather I/O?
Discuss this article in the Articles Forum topic, Gathering Scattered I/O in C++.
STLSoft
http://stlsoft.org
Pantheios
http://pantheios.org
Extended STL
http://extendedstl.com
Imperfect C++
http://imperfectcplusplus.com
ACE
http://www.cse.wustl.edu/~schmidt/ACE.html
|
Sponsored Links
|