3. Batcher odd–even mergesort metaprogramm

Batcher odd–even mergesort metaprogramm

  • ?

    SeppJ schrieb:

    GTCML schrieb:

    oha, gleich so!
    danke dir vielmals für die arbeit, ich versuche es nachzuvollziehen so gut wie möglich, sieht jedoch nicht leicht aus.

    Nanu? Ich hatte nach deiner Frage eigentlich erwartet, dass du mit TMP vertraut bist. Obiger Code ist doch relativ harmlos in dieser Hinsicht. Kleines TMP-Einmaleins gefällig?

    oh nein, das kann ich jetzt wirklich nicht auch noch annehmen. tmp ist mir bekannt und ich dürfte es auch nachvollziehen können, benötige jedoch ein bisschen zeit da es mir leider nicht so geläufig ist. wie oft macht mach denn schon was mit tmp... 😉

    0
  • Mod

    GTCML schrieb:

    wie oft macht mach denn schon was mit tmp... 😉

    Praktisch so gut wie nie, aber du hast ja (anscheinend ungewollt) direkt nach einer solchen Lösung gefragt. Die einzige Möglichkeit, auf der Templateebene Programme zu erstellen ist schließlich logischerweise Templatemetaprogrammierung.

    Dann mal viel Spaß beim Enttüfteln. Ich schätze, wenn du TMP nie gesehen hast, ist das ein echt harter Brocken, auch wenn's für den Experten ein recht einfaches Programm ist. Guck dir vielleicht zuerst einmal eine einfache Fakultätsfunktion in einer Einführung für TMP an. Das was du hier siehst ist dann nicht viel komplexer, bloß dieses Grundprinzip 3x verschachtelt (und mit structs statt Funktionen, weil man Funktionen nicht partiell spezialisieren kann).
    Aber mindestens diese Grundprinzipien der TMP musst du mal an einfachen Beispielen gesehen haben, sonst blickt man bei solchen Code nicht durch. Templatespezialisierung und Rekursion hat man ja vielleicht mal gehört, aber das ist sind ja auch so Sprachmittel, die man praktisch sonst fast nie braucht und daher den Anblick nicht gewohnt ist. Es sollte aber leicht sein, Einführungen im Netz zu finden.

    0
  • C
    Mod

    Andere Variante, den Beispielcode einigermaßen 1:1 nachgemacht

    #include <vector>
#include <iostream>

template <typename T>
using eval = typename T::type;

template <typename T> struct identity
{
   using type = T;
};

template <int... i> struct index_list : identity<index_list<i...>> {};

template <int N, int... i> struct make_index_list : make_index_list<N-1, 0, 1+i...> {};

template <int... i> struct make_index_list<0, i...> : index_list<i...> {};

template <typename... T> struct type_list : identity<type_list<T...>> {};

template <typename... T> struct merge_type_lists : merge_type_lists<eval<T>...> {};
template <typename... T, typename... U, typename... V>
struct merge_type_lists<type_list<T...>, type_list<U...>, V...>
    : merge_type_lists<type_list<T..., U...>, V...>
{};
template <typename... T>
struct merge_type_lists<type_list<T...>>
    : type_list<T...>
{};

/////////////////////////////////////
template <int a, int b>
struct index_pair
{
    static constexpr auto first = a;
    static constexpr auto second = b;
};

template <int lo, int hi, int r, typename = eval<make_index_list<(hi-lo)/(2*r)>>>
struct oddeven_merge_simple_range;
template <int lo, int hi, int r, int... I>
struct oddeven_merge_simple_range<lo, hi, r, index_list<I...>>
    : type_list<index_pair<lo+r+I*2*r,lo+2*r+I*2*r>...>
{};

template <int lo, int hi, int r>
struct oddeven_merge
    : std::conditional<(r*2<hi-lo),
                       merge_type_lists<oddeven_merge<lo, hi, 2*r>, oddeven_merge<lo+r, hi, 2*r>, oddeven_merge_simple_range<lo, hi, r>>,
                       type_list<index_pair<lo, lo+r>>>::type
{};

template <int lo, int hi>
struct oddeven_merge_sort_range
    : std::conditional<(lo<hi),
                       merge_type_lists<oddeven_merge_sort_range<lo, lo+(hi-lo)/2>, oddeven_merge_sort_range<lo+(hi-lo)/2+1,hi>, oddeven_merge<lo,hi,1>>,
                       type_list<>>::type
{};

template <typename RandomIter, typename... Pairs>
void oddeven_merge_sort(RandomIter begin, type_list<Pairs...>)
{
    bool show[] = { std::cout << '(' << Pairs::first << ',' << Pairs::second << "), "... };
    std::cout << '\n';
    bool sort[] = { ((begin[Pairs::second]<begin[Pairs::first]?std::swap(begin[Pairs::second],begin[Pairs::first]):void()),false)... };
}

template <std::size_t N, typename RandomIter>
void oddeven_merge_sort(RandomIter begin)
{
    static_assert( N>0 && (N&(N-1))==0, "N must be power of 2" );
    oddeven_merge_sort(begin, eval<oddeven_merge_sort_range<0, N-1>>{});
}

int main()
{
    std::vector<int> v = { 2, 4, 3, 5, 6, 1, 7, 8 };
    oddeven_merge_sort<8>(v.begin());
    for ( auto i : v )
        std::cout << i << '\t';
    std::cout << '\n';
}
    0
  • Mod

    camper schrieb:

    Andere Variante, den Beispielcode einigermaßen 1:1 nachgemacht

    Das sollte ich vielleicht noch erwähnen: Ich habe den Code (d.h. die abstrakte Formulierung oben auf der Seite, nicht den Beispielcode weiter unten) von
    http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/oemen.htm
    nachgemacht. Damit ist für den TE wohl leichter zu verstehen, wie man darauf kommt, da man fast alles ganz direkt übernehmen kann. Bloß die Schleife "compare [ai : ai+1] for all i element {1, 3, 5, 7, ..., n-3}" muss man rekursiv umschreiben.

    P.S.: Ich sehe gerade, der Beispielcode auf der verlinkten Seite entspricht auch fast 1:1 meinem Programm, aber eben zur Laufzeit. Es wird sogar auch der Weg über eine step_size gewählt. Ich hatte den Beispielcode unten gar nicht gesehen, da ich die Seite einfach von oben nach unten gelesen und nachprogrammiert habe.

    0
  • Mod

    Ich hab mich auch rangesetzt

    template <typename I>
	void compare_swap( I a, I b )
	{
		if (*a > *b)
			std::iter_swap(a, b);
	}

	template <std::size_t lo, std::size_t hi, std::size_t r>
	struct oddeven_merge
	{
		template <typename Iter>
		void operator()(Iter first)
		{
			call_(first, std::integral_constant<bool, step < hi - lo>{});
		}

	private:
		static auto const step = 2*r;

		template <typename Iter>
		static void call_(Iter first, std::true_type)
		{
			oddeven_merge<lo    , hi, step>{}(first);
			oddeven_merge<lo + r, hi, step>{}(first);

			for (std::size_t i = lo + r; i <= hi - r; i += step)
				compare_swap(first + i, first + i + r);
		}

		template <typename Iter>
		static void call_(Iter first, std::false_type)
		{
			compare_swap(first + lo, first + lo + r);
		}
	};

	template <std::size_t lo, std::size_t hi>
	struct oddeven_merge_sort_range
	{
		static auto const mid = lo + (hi-lo)/2;

		template <typename Iter>
		void operator()( Iter first )
		{
			oddeven_merge_sort_range<lo   , mid>{}(first);
			oddeven_merge_sort_range<mid+1, hi >{}(first);
			oddeven_merge<lo, hi, 1>{}(first);
		}
	};

	template <std::size_t lo>
	struct oddeven_merge_sort_range<lo, lo>
	{
		template <typename I> void operator()(I) {}
	};

	template <std::size_t N, typename Iter>
	void oddeven_merge_sort( Iter i )
	{
		static_assert( (N & (N-1)) == 0 && N != 0, "N must be a power of 2" );
		oddeven_merge_sort_range<0, N-1>{}(i);
	}

    Hmm.

    #include <algorithm>   // iter_swap
#include <type_traits> // integral_constant / false_type / true_type
#include <iostream>
#include <array>

namespace Arcoth
{
    // […]
}

namespace camper
{

    // […]

	struct evaluator
	{
		template <typename... Args>
		evaluator(Args&&...) {}
	};
	void evaluate(evaluator) {}

	template <typename RandomIter, typename... Pairs>
	void oddeven_merge_sort(RandomIter begin, type_list<Pairs...>)
	{
		evaluate({ ((begin[Pairs::second]<begin[Pairs::first]?std::swap(begin[Pairs::second],begin[Pairs::first]):void()),false)... });
	}

    // […]
}

namespace SeppJ
{
    // […]
}

#include <random>
#include <memory>

template <std::size_t N,
          std::size_t outer_loopings,
          std::size_t inner_loopings,
          typename T>
void test(T obj, int64_t const* values)
{
	auto best = std::numeric_limits<clock_t>::max();

	uint64_t check;

	uint64_t array[N*inner_loopings];

	for (unsigned j = 0; j != outer_loopings; ++j )
	{
		check = 0;

		std::copy_n( values, N*inner_loopings, array );

		auto start = clock();

			for (unsigned i = 0; i != inner_loopings; ++i)
			{
				obj( array + N*i );

				for (std::size_t c = 0; c != N; c += 2)
					(check += array[c]) *= array[c+1];
			}

		auto time = clock() - start;

		if (time < best)
		{
			best = time;
			j = 0;
		}
	}

	std::cout << 1. * best / CLOCKS_PER_SEC << ' ' << std::hex << check << '\n';
}

int main()
{
	auto constexpr size = 256, inner = 512, outer = 5000;

	std::uniform_int_distribution<int64_t> dis(std::numeric_limits<int64_t>::min());
	std::mt19937_64 engine( std::random_device{}() );

	int64_t values[size*inner];

	std::generate( std::begin(values), std::end(values), [&] {return dis(engine);} );

	std::cout << "SeppJ : "; test<size, outer, inner>( SeppJ::odd_even_mergesort<size>{}                       , values );
	std::cout << "camper: "; test<size, outer, inner>( [] (auto iter) {camper::oddeven_merge_sort<size>(iter);}, values );
	std::cout << "Arcoth: "; test<size, outer, inner>( [] (auto iter) {Arcoth::oddeven_merge_sort<size>(iter);}, values );
}

    clang++ -O3 -Wall -std=c++1y -mtune=native -march=native -funroll-loops ....
SeppJ : 0.006129 def6daed3282e743
camper: 0.010375 def6daed3282e743
Arcoth: 0.007321 def6daed3282e743

    Merkwürdig. Warum ist SeppJs Variante so viel schneller?

    0
  • C
    Mod

    Arcoth schrieb:

    Merkwürdig. Warum ist SeppJs Variante so viel schneller?

    Theoretisch müssten die Varianten ja eigentlich alle gleich schnell sein, weil sie alle zu einer Serie von Compare-and-swap degenerien. Evtl. wird eine Variante nicht so stark geinled?
    Poste mal bitte auf ideone, damit ich den Code nicht selbst zusammensetzen muss.
    Wäre auch interessant, ob evtl. ein einfacher Loop besser abschneidet - bei Sortiergrösse 256 dürfte der compilierte COde recht groß werden, was dann ggf. zu Problemen mit dem Cache führt.
    z.B. meine Variante ändern zu

    template <typename RandomIter, typename... Pairs>
    void oddeven_merge_sort(RandomIter begin, type_list<Pairs...>)
    {
        static constexpr auto pairs[][2] = { { Pairs::first, Pairs::second }... };
        for ( int i = 0; i != sizeof...(Pairs); ++i )
            if (begin[pairs[i][1]]<begin[pairs[i][0]])
                std::swap(begin[pairs[i][1]],begin[pairs[i][0]]));
    }
    0
  • C
    Mod

    camper schrieb:

    Arcoth schrieb:

    Merkwürdig. Warum ist SeppJs Variante so viel schneller?

    Theoretisch müssten die Varianten ja eigentlich alle gleich schnell sein, weil sie alle zu einer Serie von Compare-and-swap degenerien. Evtl. wird eine Variante nicht so stark geinled?
    Poste mal bitte auf ideone, damit ich den Code nicht selbst zusammensetzen muss.
    Wäre auch interessant, ob evtl. ein einfacher Loop besser abschneidet - bei Sortiergrösse 256 dürfte der compilierte COde recht groß werden, was dann ggf. zu Problemen mit dem Cache führt.
    z.B. meine Variante ändern zu

    template <typename RandomIter, typename... Pairs>
    void oddeven_merge_sort(RandomIter begin, type_list<Pairs...>)
    {
        static constexpr auto pairs[][2] = { { Pairs::first, Pairs::second }... };
        for ( int i = 0; i != sizeof...(Pairs); ++i )
            if (begin[pairs[i][1]]<begin[pairs[i][0]])
                std::swap(begin[pairs[i][1]],begin[pairs[i][0]]));
    }

    P.S. -march=x impliziert -mtune=x

    0
  • Mod

    Poste mal bitte auf ideone, damit ich den Code nicht selbst zusammensetzen muss.

    Ideone ist von gestern. http://coliru.stacked-crooked.com/a/a5ae97d2628fba62

    z.B. meine Variante ändern zu […]

    Es gibt keine Arrays mit placeholder-Typen.

    Ich musste dein Ding abändern zu

    static constexpr std::size_t pairs[][2] = { { Pairs::first, Pairs::second }... };
		for ( int i = 0; i != sizeof...(Pairs); ++i )
			Arcoth::compare_swap( begin[pairs[i][0]], begin[pairs[i][1]] ); // der kürze wegen

    (Wollte zuerst common_type_t benutzen, hat aber die rekursive Instantiierungstiefe gesprengt :D)

    Die Werte habe ich abgeändert;

    auto constexpr size = 64, inner = 2048, outer = 5000;

    Jetzt bekomme ich

    SeppJ : 0.00344 133a82bb543c6e04
camper: 0.004839 133a82bb543c6e04
Arcoth: 0.003673 133a82bb543c6e04

    P.S. -march=x impliziert -mtune=x

    Danke, wusst' ich nicht.

    0
  • Mod

    Behalte ich die alten Werte bei bekomme ich mit deiner neuen Variante nichts neues

    SeppJ : 0.005957 f1b8f530f52e022a
camper: 0.007964 f1b8f530f52e022a
Arcoth: 0.006955 f1b8f530f52e022a

    Übrigens, eine lustige compare-swap Implementierung:

    std::tie(a, b) = std::minmax(a, b);
    0
  • C
    Mod

    Arcoth schrieb:

    (Wollte zuerst common_type_t benutzen, hat aber die rekursive Instantiierungstiefe gesprengt :D)

    clang ist da traditionell etwas beschränkt, mit -ftemplate-depth aber in diesem Fall in den Griff zu kriegen.

    Zweckmäßiger wäre hier allerdings ein Typ, der gerade groß genug ist. Kein Grund Platz in der LUT zu verschwenden. unsigned char reicht ja.

    Mit einer kleinen Änderung der Messmethode (sonst kommt bei mir nur 0 raus) erhalte ich (http://ideone.com/B3LCuj)

    g++ 4.9.0 schrieb:

    SeppJ: 4791639 66b2c7389fd2fd4a
    camper(Loop): 5632998 66b2c7389fd2fd4a
    camper(unrolled): 4816390 66b2c7389fd2fd4a
    Arcoth: 4774074 66b2c7389fd2fd4a

    also kéine nenneswerten Unterscheide (1% ist nicht signifikant)

    clang++ 3.4.2 schrieb:

    SeppJ: 4339676 c72e03ba154529b6
    camper(Loop): 6114103 c72e03ba154529b6
    camper(unrolled): 4416267 c72e03ba154529b6
    Arcoth: 4580412 c72e03ba154529b6

    Hier spielen die Eigenarten des Compilers offenbar eine große Rolle (Zeiten zwischen den Compilern sind nicht vergleichbar).

    0
Anmelden zum Antworten