פעולות מקבילות על מערכים ב-Java 8 - תרגום

תרגום המאמר

//פעולות מערך מקביל ב-Java 8 //מאת אריק ברונו, 25 במרץ 2014 //drdobbs.com/jvm/parallel-array-operations-in-java-8/240166287 //אריק ברונו עובד במגזר הפיננסי ובבלוגים לאתר Dr. של דוב.

המהדורה החדשה של Java מקלה על אינטראקציה עם מערכים במקביל - מה שמביא לשיפור משמעותי בביצועים עם מינימום קידוד. כעת, אורקל משחררת את Java SE 8 - שזה צעד ענק קדימה מבחינת השפה. אחת התכונות החשובות של מהדורה זו היא שיפור במקביליות, שחלקן מופיעות במחלקת הבסיס java.util.Arrays. למחלקה זו נוספו שיטות חדשות, אותן אתאר במאמר זה. חלק מהם משמשים בתכונה חדשה נוספת של JDK8 - למבדות. אבל בואו ניגש לעניינים.

Arrays.paralellSort()

רבות מהתכונות של parallelSort מבוססות על אלגוריתם מיון מיזוג מקביל המפצל מערך לחלקים באופן רקורסיבי, ממיין אותם ואז משלב אותם מחדש בו-זמנית למערך סופי. השימוש בה במקום בשיטת Arrays.sort הקיימת והרציפה מביאה לשיפור בביצועים ויעילות בעת מיון מערכים גדולים. לדוגמה, הקוד שלהלן משתמש ב-sortering רציף() וב-parallel parallelSort() כדי למיין את אותו מערך נתונים: public class ParallelSort { public static void main(String[] args) { ParallelSort mySort = new ParallelSort(); int[] src = null; System.out.println("\nSerial sort:"); src = mySort.getData(); mySort.sortIt(src, false); System.out.println("\nParallel sort:"); src = mySort.getData(); mySort.sortIt(src, true); } public void sortIt(int[] src, boolean parallel) { try { System.out.println("--Array size: " + src.length); long start = System.currentTimeMillis(); if ( parallel == true ) { Arrays.parallelSort(src); } else { Arrays.sort(src); } long end = System.currentTimeMillis(); System.out.println( "--Elapsed sort time: " + (end-start)); } catch ( Exception e ) { e.printStackTrace(); } } private int[] getData() { try { File file = new File("src/parallelsort/myimage.png"); BufferedImage image = ImageIO.read(file); int w = image.getWidth(); int h = image.getHeight(); int[] src = image.getRGB(0, 0, w, h, null, 0, w); int[] data = new int[src.length * 20]; for ( int i = 0; i < 20; i++ ) { System.arraycopy( src, 0, data, i*src.length, src.length); } return data; } catch ( Exception e ) { e.printStackTrace(); } return null; } } כדי לבדוק, טענתי את הנתונים הגולמיים מהתמונה למערך, שלקח 46,083,360 בתים (ושלך יהיה תלוי בתמונות שבו תשתמש). שיטת המיון הרציף לקחה כמעט 3,000 מילישניות כדי למיין את המערך במחשב הנייד בעל 4 הליבות שלי, בעוד ששיטת המיון המקבילית ארכה כ-700 מילישניות לכל היותר. מסכים, זה לא קורה לעתים קרובות שעדכון שפה חדש משפר את ביצועי הכיתה פי 4.

Arrays.parallelPrefix()

שיטת parallelPrefix מיישמת פונקציה מתמטית שצוינה על הרכיבים של מערך באופן קולקטיבי, ומעבדת את התוצאות בתוך המערך במקביל. זה הרבה יותר יעיל בחומרה מרובת ליבות מודרנית, בהשוואה לפעולות רציפות על מערכים גדולים. ישנם יישומים רבים של שיטה זו עבור סוגים בסיסיים שונים של פעולות נתונים (לדוגמה, IntBinaryOperator, DoubleBinaryOperator, LongBinaryOperator וכן הלאה), כמו גם עבור סוגים שונים של אופרטורים מתמטיים. הנה דוגמה של ערימת מערך מקביל תוך שימוש באותו מערך גדול כמו הדוגמה הקודמת, שהסתיים תוך כ-100 אלפיות שניות במחשב הנייד בעל 4 ליבות שלי. public class MyIntOperator implements IntBinaryOperator { @Override public int applyAsInt(int left, int right) { return left+right; } } public void accumulate() { int[] src = null; // accumulate test System.out.println("\nParallel prefix:"); src = getData(); IntBinaryOperator op = new ParallelSort.MyIntOperator(); long start = System.currentTimeMillis(); Arrays.parallelPrefix(src, new MyIntOperator()); long end = System.currentTimeMillis(); System.out.println("--Elapsed sort time: " + (end-start)); } ... }

Arrays.parallelSetAll()

השיטה החדשה parallelSetAll() יוצרת מערך ומגדירה כל רכיב מערך לערך בהתאם לפונקציה שיצרה את הערכים הללו, תוך שימוש במקביל לשיפור היעילות. שיטה זו מבוססת על למבדות (שנקראות "סגירות" בשפות אחרות) (וכן, זו טעות המחבר, כי למבדות וסגרים הם דברים שונים) , ואשר מהווים תכונה חדשה נוספת של JDK8 שנדון בה במאמרים עתידיים. די יהיה לציין כי למבדות, שקל לזהות את התחביר שלהן על ידי האופרטור ->, מבצעות פעולה בצד ימין לאחר החץ עבור כל האלמנטים שעברו אליה. בדוגמה של הקוד שלהלן, הפעולה מתבצעת עבור כל אלמנט במערך, באינדקס של i. Array.parallelSetAll() יוצר רכיבי מערך. לדוגמה, הקוד הבא ממלא מערך גדול עם ערכים שלמים אקראיים: public void createLargeArray() { Integer[] array = new Integer[1024*1024*4]; // 4M Arrays.parallelSetAll( array, i -> new Integer( new Random().nextInt())); } כדי ליצור מחולל רכיבי מערך מורכב יותר (לדוגמה, כזה שייצור ערכים המבוססים על קריאות מחיישנים בעולם האמיתי), תוכל להשתמש בקוד בדומה ל- הבא: public void createLargeArray() { Integer[] array = new Integer[1024*1024*4]; // 4M Arrays.parallelSetAll( array, i -> new Integer( customGenerator(getNextSensorValue()))); } public int customGenerator(int arg){ return arg + 1; // some fancy formula here... } public int getNextSensorValue() { // Just random for illustration return new Random().nextInt(); } נתחיל ב-getNextSensorValue, שבמציאות הוא יבקש מהחיישן (לדוגמה, מדחום) להחזיר את הערך הנוכחי שלו. כאן, כדוגמה, נוצר ערך אקראי. שיטת customGenerator() הבאה מייצרת מערך של אלמנטים באמצעות לוגיקה נבחרת בהתבסס על המקרה שתבחר. הנה תוספת קטנה, אבל למקרים אמיתיים זה יהיה משהו יותר מסובך.

מה זה ספליטרטור?

תוספת נוספת למחלקה Arrays שעושה שימוש ב-concurrency ולמבדה היא ה-Spliterator, המשמש לחזרה ולפיצול מערך. ההשפעה שלו אינה מוגבלת למערכים - היא פועלת היטב גם עבור שיעורי Collection וערוצי IO. מפצלים פועלים על ידי פיצול אוטומטי של מערך לחלקים שונים, ומפצל חדש מותקן לביצוע פעולות על מערכי המשנה המקושרים הללו. שמו מורכב מאיטרטור, ש"מפצל" את עבודת התנועה-איטרציה שלו לחלקים. באמצעות אותם הנתונים שלנו, נוכל לבצע פעולה מפוצלת על המערך שלנו באופן הבא: ביצוע פעולות על הנתונים בדרך זו מנצל את ההקבלה. ניתן גם להגדיר פרמטרים של מפצל, כגון הגודל המינימלי של כל תת-מערך. public void spliterate() { System.out.println("\nSpliterate:"); int[] src = getData(); Spliterator spliterator = Arrays.spliterator(src); spliterator.forEachRemaining( n -> action(n) ); } public void action(int value) { System.out.println("value:"+value); // Perform some real work on this data here... }

זרם - עיבוד

לבסוף, מתוך מערך, אתה יכול ליצור אובייקט Stream, המאפשר עיבוד מקביל על מדגם של נתונים כמכלול, המוכלל לרצף זרם. ההבדל בין אוסף נתונים ל-Stream מ-JDK8 החדש הוא שאוספים מאפשרים לך לעבוד עם אלמנטים בנפרד כאשר סטרים לא. לדוגמה, עם אוספים, אתה יכול להוסיף אלמנטים, להסיר אותם ולהכניס אותם באמצע. רצף זרימה אינו מאפשר לך לבצע מניפולציות על אלמנטים בודדים ממערך נתונים, אלא מאפשר לך לבצע פונקציות על הנתונים כמכלול. אתה יכול לבצע פעולות שימושיות כמו חילוץ של ערכים ספציפיים בלבד (התעלמות מחזרות) מקבוצה, פעולות טרנספורמציה של נתונים, מציאת המינימום והמקסימום של מערך, פונקציות הקטנת מפה (המשמשות במחשוב מבוזר) ופעולות מתמטיות אחרות. הדוגמה הפשוטה הבאה משתמשת במקביל כדי לעבד מערך נתונים במקביל ולסכם את האלמנטים. public void streamProcessing() { int[] src = getData(); IntStream stream = Arrays.stream(src); int sum = stream.sum(); System.out.println("\nSum: " + sum); }

סיכום

Java 8 בהחלט יהיה אחד העדכונים השימושיים ביותר לשפה. התכונות המקבילות שהוזכרו כאן, lambdas והרחבות רבות אחרות יהיו נושא לסקירות אחרות של Java 8 באתר שלנו.