Mdthbs

What is the difference between 型 and 形?

How does "Te vas a cansar" mean "You're going to get tired"?

As a 16 year old, how can I keep my money safe from my mother?

How to take the beginning and end parts of a list with simpler syntax?

Blocking people from taking pictures of me with smartphone

A Word/Phrase for the Process of Classifying Something as a Sin

What does this double-treble double-bass staff mean?

What's the longest period of time over which a time lapse film has been recorded?

What gave Harry Potter the idea of writing in Tom Riddle's diary?

PhD advisor lost funding, need advice

Flight control in yawing asymmery

Can a fight scene, component-wise, be too complex and complicated?

Heating Margarine in Pan = loss of calories?

What should I call bands of armed men in Medieval Times?

Can "être sur" mean "to be about" ?

Is it okay for a ticket seller to grab a tip in the USA?

Why did Gandalf use a sword against the Balrog?

Email address etiquette - Which address should I use to contact professors?

How far did Gandalf and the Balrog drop from the bridge in Moria?

How can Radagast come across Gandalf and Thorin's company?

How can I solve for the intersection points of two ellipses?

The cat ate your input again!

How are you supposed to know the strumming pattern for a song from the "chord sheet music"?

If a digital camera can be "hacked" in the ransomware sense, how best to protect it?

How do laziness and parallelism coexist in Haskell?

What's the best name for a non-mutating “add” method on an immutable collection?Getting started with HaskellWhat is the difference between concurrency and parallelism?Memory footprint of Haskell data typesWhat is Weak Head Normal Form?Haskell: How does non-strict and lazy differ?How is foldl lazy?Lazy Evaluation and Strict Evaluation HaskellI'm confused by Haskell's lazy evaluationWhy is Haskell (GHC) so darn fast?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}

15

1

People argue that Haskell has an advantage in parallelism since it has immutable data structures. But Haskell is also lazy. It means data actually can be mutated from thunk to evaluated result.

So it seems laziness can harm the advantage of immutability. Am I wrong or does Haskell have countermeasures for this problem? Or is this Haskell's own feature?

haskell parallel-processing immutability lazy-evaluation

share|improve this question

edited 3 hours ago

Boann

38.7k1313 gold badges9393 silver badges123123 bronze badges

asked 14 hours ago

Soonwon MoonSoonwon Moon

10855 bronze badges

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  
  "data actually can be mutate from thunk to evaluated result" can you say more about what you mean here and why you believe this is true?
  
  – Thomas M. DuBuisson
  14 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Thomas wiki.haskell.org/Thunk I don't have exact information of haskell implementation, but that was the simplest solution to implement laziness and thunk as I think.
  
  – Soonwon Moon
  13 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Also : en.m.wikibooks.org/wiki/Haskell/…
  
  – Soonwon Moon
  13 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  The point is, each thread must sync the information whether the thunk is already evaluated or not. Or each thread must re evaluate the thunk. (As I think)
  
  – Soonwon Moon
  13 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Laziness often only applies to initialization - supposing you have a global lock, then you can initialize an object on a single thread and make the other threads (or promises/tasks/futures) wait and then provide an initialized, immutable, data value to the new concurrent processes. No contradiction there.
  
  – Dai
  13 hours ago
  

  
  
  
  

 | 
show 2 more comments

15

1

People argue that Haskell has an advantage in parallelism since it has immutable data structures. But Haskell is also lazy. It means data actually can be mutated from thunk to evaluated result.

So it seems laziness can harm the advantage of immutability. Am I wrong or does Haskell have countermeasures for this problem? Or is this Haskell's own feature?

haskell parallel-processing immutability lazy-evaluation

share|improve this question

edited 3 hours ago

Boann

38.7k1313 gold badges9393 silver badges123123 bronze badges

asked 14 hours ago

Soonwon MoonSoonwon Moon

10855 bronze badges

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  
  "data actually can be mutate from thunk to evaluated result" can you say more about what you mean here and why you believe this is true?
  
  – Thomas M. DuBuisson
  14 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Thomas wiki.haskell.org/Thunk I don't have exact information of haskell implementation, but that was the simplest solution to implement laziness and thunk as I think.
  
  – Soonwon Moon
  13 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Also : en.m.wikibooks.org/wiki/Haskell/…
  
  – Soonwon Moon
  13 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  The point is, each thread must sync the information whether the thunk is already evaluated or not. Or each thread must re evaluate the thunk. (As I think)
  
  – Soonwon Moon
  13 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Laziness often only applies to initialization - supposing you have a global lock, then you can initialize an object on a single thread and make the other threads (or promises/tasks/futures) wait and then provide an initialized, immutable, data value to the new concurrent processes. No contradiction there.
  
  – Dai
  13 hours ago
  

  
  
  
  

 | 
show 2 more comments

People argue that Haskell has an advantage in parallelism since it has immutable data structures. But Haskell is also lazy. It means data actually can be mutated from thunk to evaluated result.

So it seems laziness can harm the advantage of immutability. Am I wrong or does Haskell have countermeasures for this problem? Or is this Haskell's own feature?

haskell parallel-processing immutability lazy-evaluation

share|improve this question

edited 3 hours ago

Boann

38.7k1313 gold badges9393 silver badges123123 bronze badges

asked 14 hours ago

Soonwon MoonSoonwon Moon

10855 bronze badges

share|improve this question

edited 3 hours ago

Boann

38.7k1313 gold badges9393 silver badges123123 bronze badges

asked 14 hours ago

Soonwon MoonSoonwon Moon

10855 bronze badges

share|improve this question

edited 3 hours ago

Boann

38.7k1313 gold badges9393 silver badges123123 bronze badges

asked 14 hours ago

Soonwon MoonSoonwon Moon

10855 bronze badges

edited 3 hours ago

Boann

38.7k1313 gold badges9393 silver badges123123 bronze badges

edited 3 hours ago

Boann

38.7k1313 gold badges9393 silver badges123123 bronze badges

asked 14 hours ago

Soonwon MoonSoonwon Moon

10855 bronze badges

asked 14 hours ago

Soonwon MoonSoonwon Moon

10855 bronze badges

1 Answer
1

active

oldest

votes

18

Yes, GHC’s RTS uses thunks to implement non-strict evaluation, and they use mutation under the hood, so they require some synchronisation. However, this is simplified due to the fact that most heap objects are immutable and functions are referentially transparent.

In a multithreaded program, evaluation of a thunk proceeds as follows:

• The thunk is atomically^† replaced with a BLACKHOLE object




• If the same thread attempts to force the thunk after it’s been updated to a BLACKHOLE, this represents an infinite loop, and the RTS throws an exception (<<loop>>)




• If a different thread attempts to force the thunk while it’s a BLACKHOLE, it blocks until the original thread has finished evaluating the thunk and updated it with a value




• When evaluation is complete, the original thread atomically^† replaces the thunk with its result

^† e.g., using a compare-and-swap (CAS) instruction

So there is a potential race here: if two threads attempt to force the same thunk at the same time, they may both begin evaluating it. In that case, they will do some redundant work—however, one thread will succeed in overwriting the BLACKHOLE with the result, and the other thread will simply discard the result that it calculated, because its CAS will fail.

Safe code cannot detect this, because it can’t obtain the address of an object or determine the state of a thunk. And in practice, this type of collision is rare for a couple of reasons:

• Concurrent code generally partitions workloads across threads in a manner suited to the particular problem, so there is low risk of overlap




• Evaluation of thunks is generally fairly “shallow” before you reach weak head normal form, so the probability of a “collision” is low

So thunks ultimately provide a good performance tradeoff when implementing non-strict evaluation, even in a concurrent context.

share|improve this answer

answered 9 hours ago

Jon PurdyJon Purdy

40.3k77 gold badges7575 silver badges131131 bronze badges

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  
  The first step isn't quite right, because GHC uses lazy blackholing (a different sense of "lazy" from the usual one). See the section "Black holes and revelations" in mainisusuallyafunction.blogspot.com/2011/10/…
  
  – dfeuer
  8 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  Consider including a link to the paper with all the gory details, Haskell on a Shared-Memory Multiprocessor. A lot of time is spent discussing very low level details that are relevant to making the result ultimately go fast in practice.
  
  – Alexis King
  51 mins ago
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f57454648%2fhow-do-laziness-and-parallelism-coexist-in-haskell%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

18

Yes, GHC’s RTS uses thunks to implement non-strict evaluation, and they use mutation under the hood, so they require some synchronisation. However, this is simplified due to the fact that most heap objects are immutable and functions are referentially transparent.

In a multithreaded program, evaluation of a thunk proceeds as follows:

• The thunk is atomically^† replaced with a BLACKHOLE object




• If the same thread attempts to force the thunk after it’s been updated to a BLACKHOLE, this represents an infinite loop, and the RTS throws an exception (<<loop>>)




• If a different thread attempts to force the thunk while it’s a BLACKHOLE, it blocks until the original thread has finished evaluating the thunk and updated it with a value




• When evaluation is complete, the original thread atomically^† replaces the thunk with its result

^† e.g., using a compare-and-swap (CAS) instruction

So there is a potential race here: if two threads attempt to force the same thunk at the same time, they may both begin evaluating it. In that case, they will do some redundant work—however, one thread will succeed in overwriting the BLACKHOLE with the result, and the other thread will simply discard the result that it calculated, because its CAS will fail.

Safe code cannot detect this, because it can’t obtain the address of an object or determine the state of a thunk. And in practice, this type of collision is rare for a couple of reasons:

• Concurrent code generally partitions workloads across threads in a manner suited to the particular problem, so there is low risk of overlap




• Evaluation of thunks is generally fairly “shallow” before you reach weak head normal form, so the probability of a “collision” is low

So thunks ultimately provide a good performance tradeoff when implementing non-strict evaluation, even in a concurrent context.

share|improve this answer

answered 9 hours ago

Jon PurdyJon Purdy

40.3k77 gold badges7575 silver badges131131 bronze badges

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  
  The first step isn't quite right, because GHC uses lazy blackholing (a different sense of "lazy" from the usual one). See the section "Black holes and revelations" in mainisusuallyafunction.blogspot.com/2011/10/…
  
  – dfeuer
  8 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  Consider including a link to the paper with all the gory details, Haskell on a Shared-Memory Multiprocessor. A lot of time is spent discussing very low level details that are relevant to making the result ultimately go fast in practice.
  
  – Alexis King
  51 mins ago
  

  
  
  
  

add a comment | 

18

Yes, GHC’s RTS uses thunks to implement non-strict evaluation, and they use mutation under the hood, so they require some synchronisation. However, this is simplified due to the fact that most heap objects are immutable and functions are referentially transparent.

In a multithreaded program, evaluation of a thunk proceeds as follows:

• The thunk is atomically^† replaced with a BLACKHOLE object




• If the same thread attempts to force the thunk after it’s been updated to a BLACKHOLE, this represents an infinite loop, and the RTS throws an exception (<<loop>>)




• If a different thread attempts to force the thunk while it’s a BLACKHOLE, it blocks until the original thread has finished evaluating the thunk and updated it with a value




• When evaluation is complete, the original thread atomically^† replaces the thunk with its result

^† e.g., using a compare-and-swap (CAS) instruction

So there is a potential race here: if two threads attempt to force the same thunk at the same time, they may both begin evaluating it. In that case, they will do some redundant work—however, one thread will succeed in overwriting the BLACKHOLE with the result, and the other thread will simply discard the result that it calculated, because its CAS will fail.

Safe code cannot detect this, because it can’t obtain the address of an object or determine the state of a thunk. And in practice, this type of collision is rare for a couple of reasons:

• Concurrent code generally partitions workloads across threads in a manner suited to the particular problem, so there is low risk of overlap




• Evaluation of thunks is generally fairly “shallow” before you reach weak head normal form, so the probability of a “collision” is low

So thunks ultimately provide a good performance tradeoff when implementing non-strict evaluation, even in a concurrent context.

share|improve this answer

answered 9 hours ago

Jon PurdyJon Purdy

40.3k77 gold badges7575 silver badges131131 bronze badges

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  
  The first step isn't quite right, because GHC uses lazy blackholing (a different sense of "lazy" from the usual one). See the section "Black holes and revelations" in mainisusuallyafunction.blogspot.com/2011/10/…
  
  – dfeuer
  8 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  Consider including a link to the paper with all the gory details, Haskell on a Shared-Memory Multiprocessor. A lot of time is spent discussing very low level details that are relevant to making the result ultimately go fast in practice.
  
  – Alexis King
  51 mins ago
  

  
  
  
  

add a comment | 

Yes, GHC’s RTS uses thunks to implement non-strict evaluation, and they use mutation under the hood, so they require some synchronisation. However, this is simplified due to the fact that most heap objects are immutable and functions are referentially transparent.

In a multithreaded program, evaluation of a thunk proceeds as follows:

• The thunk is atomically^† replaced with a BLACKHOLE object




• If the same thread attempts to force the thunk after it’s been updated to a BLACKHOLE, this represents an infinite loop, and the RTS throws an exception (<<loop>>)




• If a different thread attempts to force the thunk while it’s a BLACKHOLE, it blocks until the original thread has finished evaluating the thunk and updated it with a value




• When evaluation is complete, the original thread atomically^† replaces the thunk with its result

^† e.g., using a compare-and-swap (CAS) instruction

So there is a potential race here: if two threads attempt to force the same thunk at the same time, they may both begin evaluating it. In that case, they will do some redundant work—however, one thread will succeed in overwriting the BLACKHOLE with the result, and the other thread will simply discard the result that it calculated, because its CAS will fail.

Safe code cannot detect this, because it can’t obtain the address of an object or determine the state of a thunk. And in practice, this type of collision is rare for a couple of reasons:

• Concurrent code generally partitions workloads across threads in a manner suited to the particular problem, so there is low risk of overlap




• Evaluation of thunks is generally fairly “shallow” before you reach weak head normal form, so the probability of a “collision” is low

So thunks ultimately provide a good performance tradeoff when implementing non-strict evaluation, even in a concurrent context.

share|improve this answer

answered 9 hours ago

Jon PurdyJon Purdy

40.3k77 gold badges7575 silver badges131131 bronze badges

share|improve this answer

answered 9 hours ago

Jon PurdyJon Purdy

40.3k77 gold badges7575 silver badges131131 bronze badges

answered 9 hours ago

Jon PurdyJon Purdy

40.3k77 gold badges7575 silver badges131131 bronze badges

answered 9 hours ago

Jon PurdyJon Purdy

40.3k77 gold badges7575 silver badges131131 bronze badges