- Boost - lists.boost.org

Re: [boost] Fixed point integer proposal
by Soren Holstebroe 25 Jun '09

25 Jun '09

> For example, does a(24bit) x b(24bit) -> c(24bit), or c(48bit)? > > My preference is to be explicit about these issues, meaning 24bit x 24bit -> > 24 bit. If you want more, you cast the operands first. Similarly there > were some questions on division. In my template N bit x N bit equals N bit per default. The number one design criteria was speed. Why would you use fixed point instead of floats if not for speed? I agree that you should be explicit if you want to promote the return type of a multiplication. That said, my template actually work with a promotion framework I wrote, where you can specify the promoted type of different kind of operations for different types. In the image processing library where the class was used, the promotion framework was set to promote N bit * N bit to 2N bit, but only up till the maximum number of bits natively supported by the CPU architecture. It was combined with an overflow check in debug mode to avoid surprises when the promotion was at the bit loft. That worked pretty well (and speedy). > My implementation also uses boost::operators. In addition, I have 2 > versions, one which the bit-widths are set at compile time, and the other > set at runtime (I use the latter to expose to python). I can't see a way to support run time bit width without sacrificing performance. Soren

3 5

Re: [boost] Linear circular buffer
by Soren Holstebroe 25 Jun '09

25 Jun '09

Hi Dean, >> The boost library contains a circular buffer template by Jan Gaspar. It > I use it just fine in my high performance applications where I > maintain the most recent N timings from API calls. Although iteration > through the dataset may be a little painful, N is not large enough for > me to notice (100 and 1000) the pain. The calls run in sub-microsecond > time and the maintenance of automatically evicting older entries gives > me (the user) a good guarantee that the data I'm getting is > consistent. I think your example is from a scenario where buffer processing is not where most of the cpu time is spent. In that case Jan Gaspars circular buffer is just fine. In fact, if what you want to do is to aggregate a linear response (like an average function), all you have to do is to look at the item going out of the buffer and item going in, you wouldn't even have to look at whats in the middle of the buffer. If your use of circular buffers is in applications, where buffer processing is what the application is all about, then sub-microseconds matter, if you are talking about 1 billion times 5 microseconds vs 1 billion times 3 microseconds. One example is bioinformatics, where you want to drag a window across the whole 3+ gigabases genome and maybe calculate some entropy measure in that window. Another is FIR filters in DSP, where you produce an output by convolving each window with a second buffer. > I agree about read performance, but I don't think you ever need to > call 'linearize' if you don't intend to build a vector out of your > circular buffer. If your buffer processing is done by an external library, then you need to linearize. In image processing and DSP, that would be a very common situation. > Iterating through the container is O(N) where N is > the size of the container, and the check for borders is O(1); In the case where your buffer processing can use the iterators, the overall complexity is the same, but the constant is not. You save a border check if your buffer is linear. > I can imagine that you can use the modulo (%) function given that you know > the initial offset of the "first" entry in the buffer, and N being the > size of the buffer Modulo is (at least in the old days) calculated as the remainder of a division. That is much slower than a border check. > How about space efficiency then? I (the user) expect to have just 100 > elements' worth of memory used when I allocate 100 elements' worth of > a circular buffer at construction time (same goes for the STL vector). First, are you sure you get 100 elements allocated when you resize a vector to 100? A vector implementation might reserve a whole chunk of memory for you when resize to make the next potential reallocation faster. Anyway, my proposal is about speed and the allocation of, lets say 100, extra elements would not be an issue in all practical high throughput application I can think of. > Linear access time is nice especially if you intend to always just go > through the whole data structure everytime -- having said this I don't > think I'd necessarily want to pay for extra space usage if I can > absolutely avoid it. I have the exact opposite priority. I would not trade performance to save a few hundred bytes, that might have been allocated anyway by the allocator (or system paging or whatever). > How do you intend to implement the internal buffer then without having > to use more memory than necessary to store the elements? As discussed, you are, as far as I know, not guaranteed that with std::vector either in most implementations. Soren

1 0

Re: [boost] Fixed point integer proposal
by Soren Holstebroe 25 Jun '09

25 Jun '09

> 2009/6/25 Andrey Upadyshev <oliora(a)gmail.com> >> >> Yes, it is very interesting. I think it will be also useful in finance calculations. >> > > Actually, on that note, would it be possible to allow an arbitrary > scale factor instead of specifying a shift? It ought to still be as > efficient for power-of-two scales, on the assumption that compilers > optimize multiplication and division by such constants... I suppose that it would indeed be possible to use an arbitrary scale. If it is unclear if the compiler will optimize correctly, it should be straight forward to implement a scaling template with power-of-two as template specializations. Soren

1 0

OLE Automation date to local_date_time conversion
by Matthew Chambers 25 Jun '09

25 Jun '09

Hello fellow boosters, Under MSVC boost::date_time supports conversion from FILETIME, so it makes sense to also support conversion from the OLE automation date format, helpfully defined at: http://msdn.microsoft.com/en-us/library/system.datetime.fromoadate.aspx > The d parameter is a double-precision floating-point number that > represents a date as the number of days before or after the base date, > midnight, 30 December 1899. The sign and integral part of d encode the > date as a positive or negative day displacement from 30 December 1899, > and the absolute value of the fractional part of d encodes the time of > day as a fraction of a day displacement from midnight. d must be a > value between negative 657435.0 through positive 2958466.0. In fact, I don't see a good reason this function can't be included in a non-MSVC build too since it doesn't depend on the Win32 API in any way. The code to handle this conversion is quite ugly. Here is my code to do it: namespace boost { namespace date_time { //! Create a time object from an OLE automation date value. /*! Create a time object from an OLE automation date value. * The oa_date parameter is a double-precision floating-point number that * represents a date as the number of days before or after the base date, midnight, * 30 December 1899. The sign and integral part of oa_date encode the date as a * positive or negative day displacement from 30 December 1899, and the absolute * value of the fractional part of oa_date encodes the time of day as a fraction of a * day displacement from midnight. oa_date must be a value between * negative 657435.0 through positive 2958466.0. */ template<class time_type> inline time_type time_from_OADATE(double oa_date) { typedef typename time_type::date_type date_type; typedef typename time_type::date_duration_type date_duration_type; typedef typename time_type::time_duration_type time_duration_type; using boost::math::modf; static const date_type base_date(1899, Dec, 30); static const time_type base_time(base_date, time_duration_type(0,0,0)); int dayOffset, hourOffset, minuteOffset, secondOffset; double fraction = fabs(modf(oa_date, &dayOffset)) * 24; // fraction = hours fraction = modf(fraction, &hourOffset) * 60; // fraction = minutes fraction = modf(fraction, &minuteOffset) * 60; // fraction = seconds modf(fraction, &secondOffset); time_type t(base_time); t += time_duration_type(hourOffset, minuteOffset, secondOffset); t += date_duration_type(dayOffset); return t; } } } Here are some basic unit tests: template<typename time_type> void test_time_from_OADATE(std::ostream* os_ = NULL) { typedef typename time_type::date_type date_type; typedef typename time_type::date_duration_type date_duration_type; typedef typename time_type::time_duration_type time_duration_type; using namespace boost::date_time; if (os_) *os_ << "OADATE: 0.0 -> " << time_from_OADATE<time_type>(0.0) << endl; unit_assert(time_from_OADATE<time_type>(0.0) == time_type(date_type(1899, Dec, 30), time_duration_type(0,0,0))); if (os_) *os_ << "OADATE: 1.0 -> " << time_from_OADATE<time_type>(1.0) << endl; unit_assert(time_from_OADATE<time_type>(1.0) == time_type(date_type(1899, Dec, 31), time_duration_type(0,0,0))); if (os_) *os_ << "OADATE: -1.0 -> " << time_from_OADATE<time_type>(-1.0) << endl; unit_assert(time_from_OADATE<time_type>(-1.0) == time_type(date_type(1899, Dec, 29), time_duration_type(0,0,0))); if (os_) *os_ << "OADATE: 2.0 -> " << time_from_OADATE<time_type>(2.0) << endl; unit_assert(time_from_OADATE<time_type>(2.0) == time_type(date_type(1900, Jan, 1), time_duration_type(0,0,0))); if (os_) *os_ << "OADATE: 2.25 -> " << time_from_OADATE<time_type>(2.25) << endl; unit_assert(time_from_OADATE<time_type>(2.25) == time_type(date_type(1900, Jan, 1), time_duration_type(6,0,0))); if (os_) *os_ << "OADATE: -1.25 -> " << time_from_OADATE<time_type>(-1.25) << endl; unit_assert(time_from_OADATE<time_type>(-1.25) == time_type(date_type(1899, Dec, 29), time_duration_type(6,0,0))); } I made it templated because its sibling function in boost\date_time\filetime_functions.hpp is templated, but it seems that ptime is the only stock type that will work. Local_time doesn't have the right constructors, at least. Thoughts? What's the procedure to add this officially to date_time? Thanks, -Matt Chambers

2 1

Random Numbers
by Dima 25 Jun '09

25 Jun '09

Hi all, this is my first post here. As far as I've seen boost provides standard random number generators for each distribution class. So, if you want a normally distributed class, you're automatically using Box-Mueller.... However, there are other ways of generating random numbers, such as using the inverse cumulative distribution function and evaluate it at a uniformly generated random number. It might be good to add this functionality to the library, since basically everything that is needed is there. Questions: Is this already in development? Is this something of interest? I'd be willing to participate somehow if this is not already in progress. Need first step guidance though. Best regards, Dima

2 1

[MultiArray] constness and documentation bugs
by Frank Mori Hess 25 Jun '09

25 Jun '09

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I am able to modify a const multi_array through a multi_array_ref. For example: const boost::multi_array<int, 2> myarray(boost::extents[2][2]); boost::multi_array_ref<int, 2> myarrayref(myarray); myarrayref[0][1] = 2; IMO, trying to create a multi_array_ref from a const multi_array should fail to compile, only a const_multi_array_ref should work. Also, the reference doesn't include the public inheritance between multi_array, multi_array_ref, and const_multi_array in their class synopses. It is important because it seems to be the only reason you can do conversions from multi_array to multi_array_ref or const_multi_array_ref. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) iEYEARECAAYFAkpDgtMACgkQ5vihyNWuA4VKgACg4+vF6iDMXKgROj6Wl0/sDDWl bZ8AoMDKVcGSY3SWGcRRvaxG6ik8VsPS =A71z -----END PGP SIGNATURE-----

1 0

Fixed point integer proposal
by Soren Holstebroe 25 Jun '09

25 Jun '09

Hi, Some years ago I wrote a fixed point template for transparent fixed point integer arithmetics and conversion. It worked well and performance was equal to that of native integer types, at least in MS VC++. The template takes a base type and the number of bits reserved for the fraction part and meta-programming works out boundary safe arithmetics and conversions. The template has been used in an image processing library, but lately I used it for seamless conversion of a 4+28 bit fixed point MAD-library decoded mp3-stream to the output buffer of the sound system, with a detour through a float-based sound effect. Would there be public interest in a template like that in the boost library? Soren

6 5

boost::test documentation typo
by Philippe Vaucher 25 Jun '09

25 Jun '09

Hi, The tutorial at http://www.boost.org/doc/libs/1_39_0/libs/test/doc/html/tutorials/new-year-… uingkeeps using BOOST_AUTO_EST_CASE when it obviously should be BOOST_AUTO_TEST_CASE. If no one replies to this mail saying he'll handle it I'll create a ticket on the trac. Philippe

1 0

Re: [boost] version conflicts: is there a solution?
by Artyom 25 Jun '09

25 Jun '09

There are many problems and this is not as simple as you think. Because if you have two versions of foo() defined in header files they may be exported and... collide. See: http://stackoverflow.com/questions/836875/ This problem is much more significant at UNIX platforms where all symbols are exported by default. Think of boost_1.38 boost/foo.hpp namespace boost { int foo() { return 1; } } boost_1.39 boost/foo.hpp namespace boost { int foo() { return 1; } } Now the library includes this header from 1.38 and automatically exports foo outside. Now, you use 1.39 and may get different values of foo(). You may do simple tests and find how bad this is. So... NO You can't use two versions of boost in same project especially at ELF platforms. ...... I just what to remind that there is a script I had written that renames boost namespace and macros preventing namespace collisions of two different versions of Boost. http://lists.boost.org/Archives/boost/2009/05/151816.php So take a look on it, and give feedback, so I would be able to submit it officially to Boost. Artyom > Having the definitions separated into different translation > units doesn't seem > to be enough to prevent ODR violations according to the > standard. It gives a > list of requirements for multiple definitions in different > translation units > in section 3.2.5. >

2 1

Linear circular buffer
by Soren Holstebroe 25 Jun '09

25 Jun '09

Hi, The boost library contains a circular buffer template by Jan Gaspar. It seems well written and STL robust, but I believe the design has some performance shortcomings in many practical usages. Every time I have used a circular buffer it has been to drag a window over a huge or real time dataset. If the dataset is non real-time and small enough to be contained in memory, there is no practical need for a circular buffer, since the window data pointer can just be dragged in memory along the full length of the dataset. In many algorithms using a dragged window, you would need to process the full length of the window for each time the window is moved. E.g. convolving signal data. Thus, you read from the window a lot more than you write. To maximize performance of your window reading and to utilize external libraries, you need linear access to the data. While Gaspar's circular buffer provide a linearize method, it requires a full reorganization of the contained data. This yields an O(N*M) efficiency, just for dragging the window (size N) over the data (size M). For internal use, the circular buffer provides iterators, but each iteration requires an internal buffer check, in order to wrap around the buffer border. Since the nature of a circular buffer in most practical scenarios (at least that I can think of) is to be involved in the processing of large amount of data, read performance is important. If you allow the internal buffer to allocate more memory than the size of the circular buffer, you can reduce the number of times you need to reorganize the internal buffer to make it linear readable. If you allocate N items more than the circular buffer size, you only need to reorganize every N+1 pushes to the window. Thus, allocating additional 100 items will reduce the reorganization overhead to 1%. I have written to Jan Gaspar, who recognizes that the buffer is not efficient for linear use, but he hasn't got the time anymore to add that feature. Is a circular buffer variant with linear access at a low maintenance cost something that would have public interest? Soren

2 1