Difference between revisions of "Reference Page"

From CSE231 Wiki
Jump to navigation Jump to search
 
(9 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
This is a collection of all the the different tools we use in this course and their syntax.
 
This is a collection of all the the different tools we use in this course and their syntax.
  
While this page is here to assist you whenever you forget how to create a lambda or register a phaser, try not to become too reliant on it. If you learn and understand the syntax for the tools we build in this class, it will make the assignments easier and faster to get through. Also, this page will not be available during exams, and while there is always leniency with written code, there must be some demonstration of understanding how to use our parallel constructs!
+
While this page is here to assist you whenever you forget how to create a lambda or register a phaser, try not to become too reliant on it. If you learn and understand the syntax for the tools we build in this class, it will make the assignments easier and faster to get through.
  
 
=Java Basics=
 
=Java Basics=
Line 27: Line 27:
  
 
<source>Foo userMadeObject = new Foo(1);</source>
 
<source>Foo userMadeObject = new Foo(1);</source>
 
  
 
===Ternary Operators===
 
===Ternary Operators===
Line 103: Line 102:
 
<source>Callable<V> body = () -> {
 
<source>Callable<V> body = () -> {
 
doSomething();
 
doSomething();
 +
return foo;
 
}
 
}
 
V result = body.call();</source>
 
V result = body.call();</source>
Line 168: Line 168:
 
<source>KeyValuePair<String, int> newEntry = new KeyValuePair<>("A", 1);</source>
 
<source>KeyValuePair<String, int> newEntry = new KeyValuePair<>("A", 1);</source>
  
=V5/Habanero=
+
Looping through entries is also very easy to do!
 +
 
 +
<source>Map<K,V> map = mapFilledWithEntries();
 +
for(Entry<K,V> entry: map.entrySet()){
 +
K entryKey = entry.getKey();
 +
V entryValue = entry.getValue();
 +
doSomething(entryKey, entryValue);
 +
}</source>
  
Habanero is [http://pasiphae.cs.rice.edu/ Rice's] collection of parallel tools. When you watch the RiceX videos, it is the Habanero version of things you will be seeing. For this course, we've designed [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/edu/wustl/cse231s/v5/V5.html V5]. It is similar to Habanero in most ways, but has small changes to hopefully make your lives easier when it comes to using the tools in this class. Listed below is the syntax for V5's version, but the differences between the two versions are noted to help clarify.
+
=ForkJoin=
  
===Async===
+
===Fork===
  
Asyncs are a fundamental building block of task level parallelism. The execution of an async will spawn a new child task, and any code written within the braces of an async will be done in that new task parallel to the parent task. The actual [https://www.cse.wustl.edu/~cosgroved/courses/cse231/summer18/apidocs/edu/wustl/cse231s/v5/V5.html#async-edu.wustl.cse231s.v5.api.CheckedRunnable- async] method is called like this:
+
Forks are a fundamental building block of task level parallelism. The execution of an fork will spawn a new child task, and any code written within the braces of an async will be done in that new task parallel to the parent task.
<code>async(Runnable body)</code>
 
  
But as discussed above in the [[#Runnable|Runnable]] section, a Runnable can be defined just using a [[#Lambda|lambda]]. For the runnables in asyncs, there are no parameters passed in, so an async with the lambda is as follows:
+
The fork method accepts a [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/spring22/apidocs/fj/api/TaskSupplier.html TaskSupplier<T>].  But as discussed above in the [[#Runnable|Runnable]] section, a TaskSupplier<T> can be defined just using a [[#Lambda|lambda]]. For the runnables in forks, there are no parameters passed in, so an fork with the lambda is as follows:
  
<source>async( () -> {
+
<source>Future<T> future = fork( () -> {
doSomething();
+
return doSomething();
 
});
 
});
 
doSomethingElse();</source>
 
doSomethingElse();</source>
  
In the above example, both <code>doSomething()</code> and <code>doSomethingElse()</code> are being done at the same time as one another.
+
In the above example, both <code>doSomething()</code> can run before, after, or at the same time as <code>doSomethingElse()</code>.
 
+
<!--
 
It is also worth noting that with V5, we can use asyncs ''without'' having a new task spawn. This can be really helpful when building and debugging your programs, as it will give you quick and simple means to switch back and forth between parallel and sequential. To do this, use the following version of the method: <code>async(Boolean isParallelDesired, Runnable body)</code>. In the following example, switching the first line can switch whether or not the two things are run in parallel or not!
 
It is also worth noting that with V5, we can use asyncs ''without'' having a new task spawn. This can be really helpful when building and debugging your programs, as it will give you quick and simple means to switch back and forth between parallel and sequential. To do this, use the following version of the method: <code>async(Boolean isParallelDesired, Runnable body)</code>. In the following example, switching the first line can switch whether or not the two things are run in parallel or not!
  
Line 193: Line 199:
 
});
 
});
 
doSomethingElse();</source>
 
doSomethingElse();</source>
 +
-->
  
===Finish===
+
===Join===
  
Finish blocks will wait until everything within the brackets (no matter the number of tasks) executes and completes before moving on to any of the code after it. This is essential in preventing data races and will be used frequently in the course.
+
Joins will wait until the Future(s) which is/are passed to it have completed. This is essential in preventing some race conditions and will be used in almost every imaginably correct program.
  
<code>finish(Runnable body)</code>
+
<source>Future<T> future = fork( () -> {
<source>finish( () -> {
+
return doSomething();
async( () -> {
 
doSomething();
 
});
 
asynch( () -> {
 
doSomethingElse();
 
});
 
 
});
 
});
doMoreSomethingElses();</source>
+
doSomethingElse();
 +
T value = join(future);
 +
doYetAnotherThing();
 +
</source>
 +
 
 +
In this example, <code>doSomething()</code> and <code>doSomethingElse()</code> can run in parallel with each other, but <code>doYetAnotherThing()</code> will not begin until <code>doSomething()</code> and <code>doSomethingElse()</code> have fully completed. 
  
In this example, <code>doSomething();</code> and <code>doSomethingElse();</code> will run in parallel with each other, but <code>doMoreSomethingElses();</code> will not begin until the first two things have fully completed.  
+
Further, the return value of doSomething() will be assigned to <code>value</code>.
  
 +
Note: <code>doSomething()</code> will have completed because of the join on its Future.  <code>doSomethingElse()</code> will have completed because of the normal continuation of a sequential strand.
 +
 +
<!--
 
===Parallel Loops===
 
===Parallel Loops===
 
{{Warning| CSE 231s is all exclusive max, all the time.  forall, forasync, and forseq are all exclusive max.}}
 
{{Warning| CSE 231s is all exclusive max, all the time.  forall, forasync, and forseq are all exclusive max.}}
Line 218: Line 227:
 
A forall loop is a simplified way to do the following:
 
A forall loop is a simplified way to do the following:
  
<source>finish((), -> {
+
<source>finish(()-> {
 
for(int i = minInclusive; i < maxExclusive; i++){
 
for(int i = minInclusive; i < maxExclusive; i++){
 
final int i_ = i;
 
final int i_ = i;
Line 351: Line 360:
 
*Some other NumberReductionOperators you can use are <code>PRODUCT</code>, <code>MIN</code>, and <code>MAX</code>.
 
*Some other NumberReductionOperators you can use are <code>PRODUCT</code>, <code>MIN</code>, and <code>MAX</code>.
 
*Some other types of accumulators are <code>newDoubleFinishAccumulator()</code> and <code>newReducerFinishAccumulator</code>
 
*Some other types of accumulators are <code>newDoubleFinishAccumulator()</code> and <code>newReducerFinishAccumulator</code>
 
+
-->
 
=Java Util Concurrent=
 
=Java Util Concurrent=
 
X10 is Java's built in parallel tools. These are some things you will always be able to use outside of this course. If you have questions on how certain things work, searching for the javadocs for any object or class will normally provide the answers.
 
X10 is Java's built in parallel tools. These are some things you will always be able to use outside of this course. If you have questions on how certain things work, searching for the javadocs for any object or class will normally provide the answers.
Line 413: Line 422:
 
doSomething(i);
 
doSomething(i);
 
phaser.arriveAndAwaitAdvance();
 
phaser.arriveAndAwaitAdvance();
}</source>
 
 
===Synchronized===
 
 
Synchronizing on something prevents on any other thread using (and thus modifying) the synchronized object until it has finished executing the code in the block. You can synchronize on as big or small an object you want. The example below, both uses of synchronized will make the class thread safe, but they have different performance implications.
 
 
<source>public class Foo{
 
public List<T> list;
 
 
public Foo(){
 
this.list = new LinkedList<>();
 
}
 
 
public void addToList(){
 
synchronized(this){
 
this.list.add(new T());
 
}
 
}
 
 
public void removeFromList(){
 
synchronized(this.list){
 
this.list.poll();
 
}
 
}
 
 
}</source>
 
}</source>
  

Latest revision as of 03:59, 4 April 2023

This is a collection of all the the different tools we use in this course and their syntax.

While this page is here to assist you whenever you forget how to create a lambda or register a phaser, try not to become too reliant on it. If you learn and understand the syntax for the tools we build in this class, it will make the assignments easier and faster to get through.

Java Basics

Sometimes the problem isn't with doing things in parallel, but just getting Java to cooperate with what you want it to do. This section should hopefully help you figure out how to use the Java concepts needed to complete the assignments in the class.

This page mainly just covers syntax though. For a better understanding of how some of these tools actually function and why we use them, check out Rundown on Everything Java.

Object Constructors

There will be a lot of classes for students to make/complete throughout the semester. Many times, you will be responsible for filling out the constructor. If given something like this:

private int value;

public Foo(int parameter){
	//TO DO
}

While all sorts of code and commands may be used in the constructor, before it is over, all of the class's private variables should have been assigned.

public Foo(int parameter){
	this.value = parameter;
}

Then, outside of this class, you can create an object of type Foo by doing the following:

Foo userMadeObject = new Foo(1);

Ternary Operators

A handy and quick way to do things based on a boolean operation. The two blocks of code are equivalent.

if(testCondition){
	int finalResult = valueIfTrue;
} else{
	int finalResult = valueIfFalse;
}
int finalResult = (testCondition) ? valueIfTrue : valueIfFalse

For-each Loop

For loops don't always need to go from one integer to the next. In fact, if we have any iterable object (array, list, set, etc.), we can just loop through all the entries available in that object. Use this to make your life much simpler!

List<T> filledList;
for(T singleEntry: filledList){
	doSomething(singleEntry);
}

Runtime

In order to get the number of processors your computer has:

int numProcessors = Runtime.getRuntime().availableProcessors();

Generics

Check out the dedicated Generics page for a deep dive on how Java's generic types work!

Interfaces

Check out the dedicated Interfaces page for an in-depth discussion on interfaces in Java!

Lambda

Lambdas are very complex things, and they are also incredibly important when it comes to understanding how our code works in this course. If you are looking for more information on what lambdas actually are, go check out the Lambdas wiki page, or the lambdas section in the Rundown on Everything Java page!

The syntax for a lambda can be seen as:

(T parameter) -> {
	doSomething();
}

Within the curly braces, you will have access to that parameter variable. Most times you use lambdas though, there are no parameters to pass through, so you can just do

() -> {
	doSomething();
}

It's strongly encouraged to check out the Eclipse tip on how to use content assist lambdas.

Anonymous Classes

We use anonymous classes throughout the course as a convenient way to instantiate objects of classes that have methods we need to define. There are two ways to do this, one manually labeling the method we're defining, and one with lambda. These are two similar creations of a Function object (which has the method "apply") that adds one to whatever number is passed in:

Function<Integer, Integer> increment = new Function<Integer, Integer>{
	public Integer apply(Integer oldValue){
		return oldValue + 1;
	}
};
Function<Integer, Integer> increment = (oldValue) -> {
	return oldValue + 1;
};

Since the class we are defining only has one method, if we use a lambda, it knows that the lambda refers to that one specific method. Check out the section on [Lambdas#Anonymous_Classes|Anonymous Classes] for more information!

Runnable

A Java Runnable is an object with just a .run() method. As discussed above, that means we can instantiate a Runnable using an anonymous class created by a lambda.

Runnable body = () -> {
	doSomething();
}
body.run();

Callable

A Java Callable is very similar to a Runnable. It is an object with only a .call() method. A key difference between this and a Runnable is that a Callable has a return value when called.

Callable<V> body = () -> {
	doSomething();
	return foo;
}
V result = body.call();

Java Basic Util Data Structures

Java's Data Structures are a core part of this class, as we will be constantly working with data and making our own data. In no time at all will you become very familiar with some of the more useful data structures!

Remember that mainly syntax is shown here, with Rundown on Everything Java being the best place to go for more detailed information on certain topics.

Lists

Many times you will need to make some kind of list to keep information in. The two we recommend using are Linked Lists and Array Lists.

List<T> listA = new LinkedList<>();
List<T> listB = new ArrayList<>();

List Iterator

All lists (and many other objects) have iterators we can use to easily traverse through the list.

List<T> list;
ListIterator<T> iterator = list.listIterator();
while(iterator.hasNext){
	T itemA = iterator.next();
	doSomething(itemA);
}
while(iterator.hasPrevious){
	T itemB = iterator.previous();
	doSomething(itemB);
}

Maps

Many times you will need to make some kind of map to store information in. Depending on the race conditions of the assignment, you usually will use Hash Maps or Concurrent Hash Maps.

Map<K,V> map = new HashMap<>();

Compute

A very important application of a map is its compute method. This allows us to change a value in a map rather than having to remove it and add it back. Here is the code for the default implementation of the compute method, taken from the Map JavaDocs.

V oldValue = map.get(key);
V newValue = remappingFunction.apply(key, oldValue);
if (oldValue != null ) {
	if (newValue != null)
		map.put(key, newValue);
	else
		map.remove(key);
} else {
	if (newValue != null)
		map.put(key, newValue);
	else
		return null;
}

Most students tend to get tripped up on the use of a BiFunction. This BiFunction is essential giving the map a formula to use in order to get the new value it needs to set in the map. If we wanted to call compute on a key and increase its value by one (assuming the value is an integer), it would look like this:

map.compute(keyName, (key, value) -> {
	return value + 1;
}

Note that the BiFunction is simply given as a lambda with two parameters passed in. Also important is that this lambda has a return value. Whatever is returned is what the new value in the map will become.

Other methods in Map that you may find helpful are computeIfAbsent, merge, and replace. Check out the Map JavaDocs for more detailed information on how those methods work.

Entries

In a lot of assignments, you will need to make entries of different types. Almost always, the KeyValuePair<K,V> or KeyMutableValuePair<K,V> will be your best options.

KeyValuePair<String, int> newEntry = new KeyValuePair<>("A", 1);

Looping through entries is also very easy to do!

Map<K,V> map = mapFilledWithEntries();
for(Entry<K,V> entry: map.entrySet()){
	K entryKey = entry.getKey();
	V entryValue = entry.getValue();
	doSomething(entryKey, entryValue);
}

ForkJoin

Fork

Forks are a fundamental building block of task level parallelism. The execution of an fork will spawn a new child task, and any code written within the braces of an async will be done in that new task parallel to the parent task.

The fork method accepts a TaskSupplier<T>. But as discussed above in the Runnable section, a TaskSupplier<T> can be defined just using a lambda. For the runnables in forks, there are no parameters passed in, so an fork with the lambda is as follows:

Future<T> future = fork( () -> {
	return doSomething();
});
doSomethingElse();

In the above example, both doSomething() can run before, after, or at the same time as doSomethingElse().

Join

Joins will wait until the Future(s) which is/are passed to it have completed. This is essential in preventing some race conditions and will be used in almost every imaginably correct program.

Future<T> future = fork( () -> {
	return doSomething();
});
doSomethingElse();
T value = join(future);
doYetAnotherThing();

In this example, doSomething() and doSomethingElse() can run in parallel with each other, but doYetAnotherThing() will not begin until doSomething() and doSomethingElse() have fully completed.

Further, the return value of doSomething() will be assigned to value.

Note: doSomething() will have completed because of the join on its Future. doSomethingElse() will have completed because of the normal continuation of a sequential strand.

Java Util Concurrent

X10 is Java's built in parallel tools. These are some things you will always be able to use outside of this course. If you have questions on how certain things work, searching for the javadocs for any object or class will normally provide the answers.

Once again, you can find more in-depth explanations of how some of these tools work by checking out these pages:

Threads

The most simple way to do something in parallel in Java is to create and run a new thread. The constructor needs to have a run() method, so we can just use a lambda.

Thread threadToRun = () -> {
	doSomething();
}
threadToRun.start();
doSomethingElse();
threadToRun.join();

Executors

The ExecutorService class has a submit() function that returns a Future. From there, it isn't to different from our version of Future. In the following example, ExecutorService executor is passed to us.

Future<Integer> future = executor.submit(() -> {
	int value = doSomething();
	return value;
};
doSomethingElse();
future.get()

Phasers

There are a lot of things you can do with Phasers. Check out the official Javadocs for a breakdown of all the options. Here is an example that uses some of the methods we'll call when utilizing phasers.

Phaser phaserA = new Phaser();
Phaser phaserB = new Phaser();
phaserA.register()
phaserB.register()
finish(() -> {
	async(() -> {
		for(int i = 0; i < 10; i++){
			doSomething();
			phaserA.arrive();
			PhaserUtils.awaitAdvancedForPhase(phaserB, i);
		}
	});
	
	for(int j = 0; j < 10; j++){
		doSomethingElse();
		phaserB.arrive();
		PhaserUtils.awaitAdvancedForPhase(phaserA, j);
	}
});

PhaserUtils.awaitAdvancedForPhase(Phaser phaser, int phaseNumber) is a tool we have created to make it safer to wait for other phasers. You have have multiple things wait on one phaser by using a bulk register.

Phaser phaser = new Phaser();
phaser.bulkRegister(3);
forall(0, 3, (i) -> {
	doSomething(i);
	phaser.arriveAndAwaitAdvance();
}

Locks

Locks are an alternative to synchronized. With proper use of locks, we can make our methods thread safe. Here's a couple examples that showcase the syntax for locks.

Reentrant lock = ...
lock.lock();
doSomething();
lock.unlock();
Lock lock = ...
if (lock.tryLock()) {
	try {
		doSomething();
	} finally {
		lock.unlock();
	}
}