panthema (page 4 of 1 2 3 4 5 6 7 8 9 10)
Example of intuition behind the inducing process

Presented Short Paper about eSAIS at MASSIVE'13 Workshop

Posted on 2013-09-05 18:00 by Timo Bingmann at Permlink with 0 Comments. Tags: research stringology c++ talk

Today, we presented a shorter version of our work on "Inducing Suffix and LCP Arrays in External Memory" at the MASSIVE Workshop 2013, held adjacently with ESA at ALGO 2013 in Sophia Antipolis, France.

The slides of our presentation 2013-09-05 eSAIS @ MASSIVE'13.pdf 2013-09-05 eSAIS @ MASSIVE'13.pdf and the corresponding short paper massive13esais.pdf massive13esais.pdf are available online via this webpage.

Download 2013-09-05 eSAIS @ MASSIVE'13.pdf
Download massive13esais.pdf

Please refer to the first eSAIS posting for details and source code.

Our thanks goes to all the organizers for making such an inspiring workshop possible.

Small TikZ Drawing of a Pythagoras Tree

Small TikZ Drawing of a Pythagoras Tree

Posted on 2013-06-27 23:23 by Timo Bingmann at Permlink with 0 Comments. Tags: fun

This post just contains a simple TikZ/LaTeX program to construct a Pythagoras tree. I wrote it to figure out how to write recursive TikZ drawings. The rest is rather pretty.

Without further ado:

This blog entry continues on the next page ...

The Sound of Sorting demo program

Published "The Sound of Sorting" 0.6

Posted on 2013-05-22 23:50 by Timo Bingmann at Permlink with 2 Comments. Tags: c++ university fun sorting sound of sorting

This post announces the publication of my demo program for integer string sorting algorithms, called "The Sound of Sorting". It both visualizes the internals of sorting algorithms, and generates sound effects from the values being compared!

The demo is implemented using the cross-platform toolkits wxWidgets and SDL, can be executed on Windows, Linux and Mac, and runs in real time.

There are also many videos of the sorting algorithm on my new YouTube channel.

See the Sound of Sorting project page for the demo program and source code, and more information about version 0.6.

Ternary search tree used in parallel super scalar string sample sort

Released parallel-string-sorting 0.5 including Parallel Super Scalar String Sample Sort

Posted on 2013-05-08 11:47 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ parallel-string-sorting sorting

This short post announces the first public version of our parallel string sorting project. It is a test framework and algorithm collection containing many sequential and parallel string sorting implementations.

The collection includes parallel super scalar string sample sort (pS5), which we developed and showed to have the highest parallel speedups on modern multi-core shared memory systems.

See the parallel-string-sorting project page for our technical report and more information about version 0.5.

Small drawing of a B+ tree

Publishing STX B+ Tree 0.9 - Speed Gains over 0.8.6

Posted on 2013-05-07 21:16 by Timo Bingmann at Permlink with 0 Comments. Tags: stx-btree

This blog post announces the new version 0.9 of my popular STX B+ Tree library of C++ templates, speedtests and demos. Since the last release in 2011, many patches and new ideas have accumulated. Here a summary of the most prominent changes:

STX B+ tree version 0.9 is available from the usual project webpage.

The switch from binary search to linear scan, and all further patches and optimization call for a direct comparison of version 0.8.6 and 0.9. Because of special optimizations to the btree_set specializations, the following plots differentiate between set and maps.

This blog entry continues on the next page ...

Photo of my Raspberry Pi Model B

STX B+ Tree Speed Test Measurements on Raspberry Pi (Model B)

Posted on 2013-05-06 09:48 by Timo Bingmann at Permlink with 1 Comments. Tags: stx-btree frontpage

The Raspberry Pi is maybe one of the most hyped embedded system projects in the last year, and I also got myself one for experiments. People are doing amazing things with this Linux-in-a-box SoC. Doubtlessly, the popularity is due to the standardized platform and a large community forming around it, which makes fixing the many small problems with Linux on ARM systems feasible. For me, the Raspberry Pi is an alternative architecture on which to test my algorithms and libraries, which exhibits somewhat different characteristics than the highly optimized desktop CPUs.

So I decided to run my STX B+ Tree speed test on the Raspberry Pi Model B, because most people use the SoC for multimedia purposes and little other memory performance data is available. The B+ tree speed test gives insight into the platform's overall memory and processing performance, and thus yields a better assessment of how useful the system is for general purpose applications (unlike multimedia decoding). Most benchmarks focus solely on floating point or integer arithmetic, which alone are very poor indicators for overall system performance. The Raspberry Pi forums say it has performance similar to a "Pentium 2 with 300 MHz", but that is for arithmetic.

This blog entry continues on the next page ...

STX B+ Tree Measuring Memory Usage with malloc_count

Posted on 2013-05-05 09:44 by Timo Bingmann at Permlink with 2 Comments. Tags: stx-btree frontpage

Within the next few days, a new version of my popular STX B+ Tree library will be released. In light of this imminent release, I created a memory profile with my malloc_count tool, comparing the requirements of four different C++ maps with integer keys and values.

The test is really simple: create a map container, insert 8 Mi random integer key/value pairs, and destruct it. The memory profile shows the amount of memory over time as allocated via malloc() or new. The test encompasses the usual gcc STL's map which is a red-black tree, the older hash_map from gcc's STL extensions, the newer gcc C++ tr1::unordered_map, and of course the stx::btree_map with default configuration. As a reference, I also added the usual STL vector and deque (not map containers), to verify the plotting facilities.

To isolate heap fragmentation, the profiler fork()s separate process contexts before each run. To avoid problems with multiple equal random keys, the multimap variant of all containers is used. Here is the memory profile (also included in the STX B+ Tree tarball):

Memory profile of map containers

This blog entry continues on the next page ...

Animation showing binary search and linear scan

STX B+ Tree Revisiting Binary Search

Posted on 2013-05-04 12:44 by Timo Bingmann at Permlink with 0 Comments. Tags: stx-btree

While developing another piece of software, I happened to require a customizable binary search implementation, which lead me to revisit the binary search function of my quite popular STX B+ Tree implementation.

The binary search is a central component in the container, both for performance and correctness, as it is used when traversing the tree in search for a key or an insertion point. It is implemented in the find_lower() (and find_upper()) functions.

In a first step, I cleaned the implementation to use an exclusive right boundary. In this binary search variant, hi points to the first element beyond the end (with the same meaning as usual end() C++ iterator). This got rid of the special case handled after the while loop. The exclusive right boundary is also a more natural implementation variant (even though most computer science textbooks contain the inclusive version).

Having thus changed the binary search, I reran the speed tests. However, to my surprise, the performance of the library decreased slightly, but consistently. See the code diff 39580c19 and resulting speed test PDF, where solid lines are after the patch and dashed ones before.

After some research, I found a good, independent study of binary search variants by Stephan Brumme. His summary is that a linear scan is more efficient than binary search, if the keys are located in only one cache line. This (of course) explained the performance decrease I measured, as my "special case" after the search was in fact a very short linear scan of two element.

This blog entry continues on the next page ...

Thumbnail of a pie chart filling to 100%

Released disk-filltest 0.7 - Simple Tool to Detect Bad Disks by Filling with Random Data

Posted on 2013-03-27 21:32 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ utilities

This post announces the first version of disk-filltest, a very simple tool to test for bad blocks on a disk by filling it with random data. The function of disk-filltest is simple:

See the disk-filltest project page for more information about version 0.7.

Memory profile plot as generated by example in malloc_count tarball

Released malloc_count 0.7 - Tools for Runtime Memory Usage Analysis and Profiling

Posted on 2013-03-16 22:17 by Timo Bingmann at Permlink with 1 Comments. Tags: c++ coding tricks

This post announces the first version of malloc_count, a very useful tool that I have been fine-tuning in the past months. The code library provides facilities to

The code tool works by intercepting the standard malloc(), free(), etc functions. Thus no changes are necessary to the inspected source code.

See the malloc_count project page for more information about version 0.7.

Show Page: 1 2 3 4 5 6 7 8 9 10 Next >
RSS 2.0 Weblog Feed Atom 1.0 Weblog Feed Valid XHTML 1.1 Valid CSS (2.1)
Copyright 2005-2019 Timo Bingmann - Impressum