org.apache.giraph.block_app.library.striping

Class StripingUtils

java.lang.Object

org.apache.giraph.block_app.library.striping.StripingUtils

public class StripingUtils
extends Object

Utility functions for doing superstep striping. We need to make sure that partitioning (which uses mod for distributing data across workers) is independent from striping itself. So we are using fastHash function below, taken from https://code.google.com/p/fast-hash/.

Method Summary

Modifier and Type	Method and Description
static <I extends org.apache.hadoop.io.WritableComparable> Function<Predicate<I>,Block>	createSingleStripeBySendersFunction(Block block) Given a block, creates a function that will given a predicate filter calls to vertexSend function based on that predicate.
static int	fastHash(long h) Returns 32-bit hash of a given value.
static Obj2IntFunction<org.apache.hadoop.io.LongWritable>	fastHashStriping(int stripes) Fast hash-based striping for LongWritable IDs, returns a function that for a given ID returns it's stripe index.
static Int2ObjFunction<Predicate<org.apache.hadoop.io.LongWritable>>	fastHashStripingPredicate(int stripes) Fast hash-based striping for LongWritable IDs, returns a function that for a given stripe index returns a predicate checking whether ID is in that stripe.
static int	fastStripe(long value, int stripes) Returns number in [0, stripes) range, from given input value.
static <I extends org.apache.hadoop.io.WritableComparable> Block	generateStripedBlock(int stripes, Function<Predicate<I>,Block> blockGenerator, Int2ObjFunction<Int2ObjFunction<Predicate<I>>> stripeSupplier) Generate striped block, with given number of stripes, using given blockGenerator to generate block for each stripe, and using striping based on given stripeSupplier.
static Block	generateStripedBlock(int stripes, Function<Predicate<org.apache.hadoop.io.LongWritable>,Block> blockGenerator) Generate striped block, with given number of stripes, using given blockGenerator to generate block for each stripe.
static Block	stripeBlockBySenders(int stripes, Block block) Stripe given block, by calling vertexSend only in it's corresponding stripe.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

fastHash

public static int fastHash(long h)

Returns 32-bit hash of a given value. Fast and generally good hashing function, adapted from C++ implementation: https://code.google.com/p/fast-hash/

fastStripe

public static int fastStripe(long value,
                             int stripes)

Returns number in [0, stripes) range, from given input value.

fastHashStriping

public static Obj2IntFunction<org.apache.hadoop.io.LongWritable> fastHashStriping(int stripes)

Fast hash-based striping for LongWritable IDs, returns a function that for a given ID returns it's stripe index.

fastHashStripingPredicate

public static Int2ObjFunction<Predicate<org.apache.hadoop.io.LongWritable>> fastHashStripingPredicate(int stripes)

Fast hash-based striping for LongWritable IDs, returns a function that for a given stripe index returns a predicate checking whether ID is in that stripe.

generateStripedBlock

public static Block generateStripedBlock(int stripes,
                                         Function<Predicate<org.apache.hadoop.io.LongWritable>,Block> blockGenerator)

Generate striped block, with given number of stripes, using given blockGenerator to generate block for each stripe.

Parameters:

stripes - Number of stripes

blockGenerator - Function given predicate representing whether ID is in current stripe, should return Block for current stripe

Returns:

Resulting block

generateStripedBlock

public static <I extends org.apache.hadoop.io.WritableComparable> Block generateStripedBlock(int stripes,
                                                                                             Function<Predicate<I>,Block> blockGenerator,
                                                                                             Int2ObjFunction<Int2ObjFunction<Predicate<I>>> stripeSupplier)

Generate striped block, with given number of stripes, using given blockGenerator to generate block for each stripe, and using striping based on given stripeSupplier.

Parameters:

stripes - Number of stripes

blockGenerator - Function given predicate representing whether ID is in current stripe, should return Block for current stripe

stripeSupplier - Function given number of stripes, generates a function that given stripe index, returns predicate checking whether ID is in that stripe.

Returns:

Resulting block

stripeBlockBySenders

public static Block stripeBlockBySenders(int stripes,
                                         Block block)

Stripe given block, by calling vertexSend only in it's corresponding stripe. All other methods are called number of stripes times.

Parameters:

stripes - Number of stripes

block - Block to stripe

Returns:

Resulting block

createSingleStripeBySendersFunction

public static <I extends org.apache.hadoop.io.WritableComparable> Function<Predicate<I>,Block> createSingleStripeBySendersFunction(Block block)

Given a block, creates a function that will given a predicate filter calls to vertexSend function based on that predicate. Useful to be combined with generateStripedBlock to stripe blocks.