Knit Plotter

About
Icons made by
Elegant Themes
from
www.flaticon.com
is licensed by
CC 3.0 BY
Icons made by
Dave Gandy
from
www.flaticon.com
is licensed by
CC 3.0 BY
Icons made by
Madebyoliver
from
www.flaticon.com
is licensed by
CC 3.0 BY
Icons made by
Hanan
from
www.flaticon.com
is licensed by
CC 3.0 BY
Icons made by
Yannick
from
www.flaticon.com
is licensed by
CC 3.0 BY
Icons made by
Dave Gandy
from
www.flaticon.com
is licensed by
CC 3.0 BY
Icons made by
Freepik
from
www.flaticon.com
is licensed by
CC 3.0 BY


SPRITE is a non-Interactive Frame displaying a Warcraft 3 model and loops it's animation. Changing the Parent of a Sprite during the game can bug, speeding up the displayed animation. Game Pause does not stop the animation
BlzFrameSetSpriteAnimate birth = 0 death = 1 stand = 2 morph = 3 alternate = 4


Overview
Top Companies Hire Our Student
This is a 3 month Training and Placement program designed specially to create to top tech talent in India.  Becoming great Full Stack Developer takes more than just coding, here you will learn Industry standard by the experts from Industry itself and learn to think and build like professional developer. Learn by building live company Projects. Through an advanced curriculum and project based structure, you will learn today’s cutting edge development technologies, and it’s proven by the companies like Samsung, Accenture, JP Morgan Chase and many more who hires our grads.
Interactive Classroom
This program being offline gives you complete freedom to interact, Doubt solving and learn with 100% conversion rate. Direct interaction with top tech engineers and recruiters.
Learn from Industry Experts
Learn from the people who are already doing it. Our Faculty comes from top tech companies in world including, Facebook, Dream11, Appivo and many more. Awarded as one of the finest trainer and public speaker.
Learn by doing it
You will be coding from Day 1. We have project first approach, we believe you won’t learn unless get your hands dirty. Weekly assignments, Live projects to be added in your resumes.
Profile and Job
Throughout the bootcamp we will be focusing on your profile development, resume, git, Linkedin, Projects, Interviews and Soft skill. After graduation you will start your Job hunt to find the right company.
Curriculum
Front end
Module 1:
The course starts with an understanding of how the language works. Then moving to HTML5 and CSS3, both are used for creating beautiful responsive website for any devices.
Module 2:
Learn everything from JavaScript language fundamentals to advanced topics, including objects, functions, and the browser’s document object model.
Web App
Module 3:
ReactJS and Redux is used to build a successful Client-Side Application Developer. You'll master the concepts of ReactJS including its Architecture and components. The course also focuses on Testing Redux, React Router, React Redux, JSX, Data Flow & Usage with React , Async Actions & Flow and React Middleware thereby making you completely ready to build ReactJS applications effectively.
Back End
Database
Profile Building
Portfolio
The projects you build will create an amazing portfolio that showcases your skills and experience. You will be building two live industry level project.
LinkedIn profile
We will help you write a software engineering profile that will really stand out from the crowd
Github
Strong github Profile attracts to recruiter. You need an amazing Github profile to stand out.
Resume
You will work with our Career Success Team to craft an elegant resume that shows off your skills as a full stack software engineer.
We will help you get ready for technical interviews by doing practice interviews and working through dozens of sample technical questions.
And we will introduce you to our hiring partners at top technology firms, to find opportunities that might be a good fit.
Our graduates get hired by industry leaders:
Admission
Our Admissions Process
The goal of admissions is to make sure you're ready for the challenges of the program, and that Coding Dojo is the right fit for you. We look for the innovation, how well you work with others, and perseverance.
Tuition Fees
Cohort starts every Month.
Date: 4th May | Mumbai | Rs. 30,000/-
Date: 1st June | Mumbai | Rs. 30,000/-
Installment System available on request.


TECTONIC PLATES
A Film Review by James Berardinelli
RATING: *1/2 OUT OF ****
Canada, 1992 MPAA Rating: Not Rated (Sexual themes, female topless nudity, occasional profanity) Running Length: 1:45 Theatrical Aspect Ratio: 1.33:1
Principal Cast: Marie Gignac, Robert Lapage, Celine Bonnier Director/Screenwriter: Peter Mettler Based on the play by Robert Lapage In English and French with subtitles
TECTONIC PLATES is an incredibly painful motion picture experience that nearly prompted me to walk out 20 minutes into the movie. The film (which opened in Canada during 1992 but was never released in the United States) is based on a 1988 stage play by Canadian auteur Robert Lapage, and, while it's evident that this could be a fascinating live production, the translation to the screen is a creative disaster. Enduring TECTONIC PLATES is like sitting through a filmed version of performance art -- lifeless and tedious. The qualities that make it captivating when seen in person are effaced in the motion picture medium.
TECTONIC PLATES has a storyline, although the narrative is developed in a decidedly non-traditional fashion, with shots of the stagebound play intercut with more typical cinematic sequences. It's not an inherently uninteresting way to present a movie (despite the valid complaint that it is pretentious, all-but-screaming, "Look! Art!"), although it keeps the audience distanced from the characters. Because we're constantly made aware that we're watching a play or a movie, it's impossible to accept these individuals as anything more than mouthpieces for the writer's ideas. They're not real, sympathetic, or believable. I'm willing to give director Peter Mettler credit for trying something different, but this particular experiment is not a success.
TECTONIC PLATES opens by introducing us to Madeleine (Marie Gignac), an art student studying in Montreal who has fallen in love with her professor, Jacques (Lapage). One day, he disappears, and, fearing that he left because she was undeserving of his love, Madeleine travels to Venice to kill herself. While preparing to commit suicide, she encounters drug addict Constance (Celine Bonnier), who causes Madeleine to re-think her decision. Meanwhile, Jacques has moved to New York City, where he starts cross-dressing, calls himself Jennifer, and becomes a successful counter-culture talkshow host. With settings that shift from Paris to Venice to Montreal to Manhattan to Scotland, supporting characters that include a topless goddess and a deaf/mute, and cultural references that point to Chopin, George Sand, and Jim Morrison, TECTONIC PLATES is unique, if nothing else.
However, as interesting as the film sounds (and I was excited to see it because the synopsis is promising), it never really delivers. The tone is soporific, the supposedly-intellectual prattle is inane and uninteresting, the plot meanders in a pointless and irritating manner (although it doesn't take long for the viewer to determine that the story is largely unimportant), and the symbolism is obvious. TECTONIC PLATES is trying to show that human interaction is as volatile as unpredictable as the shifting of the Earth, but it takes one-hundred minutes to get across this transparent point. There are some worthwhile moments, such as a silly sword fight between Jacques and the topless goddess and an entertaining discussion in both French and English about the differences between the two languages (although the fine points will certainly be lost on those who aren't bilingual). The only people likely to enjoy TECTONIC PLATES are those who feel a strong need to praise something this rootless and boring because (a) it's different, (b) it's not like anything they've seen before, and (c) it's pretentious. For everyone else, it's not only a waste of time, but a poor introduction to the work of Robert Lapage.
Copyright 1998 James Berardinelli
- James Berardinelli e-mail<EMAIL_ADDRESS>Now with more than 1400 reviews... The ReelViews web site: http://movie-reviews.colossus.net/
"My belief is that no movie, nothing in life, leaves people neutral.
-- David Puttnam
The review above was posted to the
rec.arts.movies.reviews newsgroup (de.rec.film.kritiken for German reviews).
The Internet Movie Database accepts no responsibility for the contents of the
review and has no editorial control. Unless stated otherwise, the copyright
belongs to the author.
Please direct comments/criticisms of the review to relevant newsgroups.
Broken URLs inthe reviews are the responsibility of the author.
The formatting of the review is likely to differ from the original due
to ASCII to HTML conversion.
Related links: index of all rec.arts.movies.reviews reviews


WEEK 8 WEDNESDAY
Year 1 (Year 2)
FIRST READING Sirach 36:1-2.5-6.13-19
A reading from the Book of Sirach
Have mercy upon us, O Lord, the God of all, and
look upon us, and show us the light of your mercy; send fear of you upon the
nations, and let them know you, as we have known that there is not God but
you, O Lord. Show signs anew, and work further wonders. Gather all the tribes
of Jacob, and give them their inheritance, as at the beginning. Have mercy, O
Lord, upon the people called by your name, upon
The word of the Lord
RESPONSORIAL PSALM Psalm 79:<IP_ADDRESS> (R. Sirach 36:1b)
R. Show us, O Lord, the light of your mercy.
Do not remember against us the guilt of former times.
Let your compassion hasten to meet us; for we have been brought very low.
R. Show us, O Lord, the light of your mercy.
Help us, O God our saviour, for the sake of the
glory of your name. Free us and forgive us our sins, because of your name.
R. Show us, O Lord, the light of your mercy.

Then we, your people, the flock of your pasture,
will give you thanks for ever and ever. From age to age we will recount your
praise.
R. Show us, O Lord, the light of your mercy.
FIRST READING 1 Peter 1:18-25
Beloved: You know that you were ransomed from the futile ways inherited from your fathers, not with perishable things such as silver or gold, but with the precious blood of Christ, like that of a lamb without blemish or spot. He was destined before the foundation of the world but was made manifest at the end of the times for your sake. Through him you have confidence in God, who raised him from the dead and gave him glory, so that your faith and hope are in God. Having purified your souls by your obedience to the truth for a sincere love of the brethren, love one another earnestly from the heart. You have been born anew, not of perishable seed but of imperishable, through the living and abiding word of God; for "All flesh is like grass and all its glory like the flower of grass. The grass withers, and the flower falls, but the word of the Lord abides for ever." That word is the good news which was preached to you.
The word of the Lord
RESPONSORIAL PSALM Psalm 147
R. O
O Jerusalem, glorify the LORD! O Sion, praise your God!  He sends out his word to the earth, and swiftly runs
his command.
R. O
He reveals his word to Jacob; to
R. O
R. Alleluia. The Son of Man came not to be served but to serve, and to give his life as a ransom for many. R. Alleluia.
GOSPEL Mark 10:32-45
A reading from the holy Gospel according to Mark
At that time: The disciples were on the road, going
up to
The Gospel of the Lord.


What is HTML and CSS?
HTML and CSS are both considered front-end development. What front-end development is everything the user sees. This is known as client-side programming which is what the user actually sees. For example, front-end development consists of things like fonts, drop-down menus, buttons, transitions, sliders, contact forms, etc. Now having the basic understanding of Front-end Development, I can explain to you HTML and CSS.
HTML
HTML stands for Hyper Text Markup Language. HTML is the language use to structure yourwebsite along with all the contents in it. It consists of short code short codes typed into a text-file by the user. HTML tells the web browser how to display the content and images to the user. The tools in HTML are called tags. Tags are tools in HTML that allows the user to add images, videos and audio clips. An example of what one of the HTML tags:

Hello World!

This is going to be a long paragraph

The “
” tag stands for a header, thus the “h”. The “2” stands for the level of the header. The “
” tag stands for paragraph format. These are some examples of HTML.
CSS
CSS stands for Cascading Style Sheets. CSS is a style sheet language used for describing the presentation of a document written in a HTML. It allows you to specify things like the font you want on your page, the size of your text, whether the page is to have 2 columns, whether your text is to be in bold or italics, and so on. It pretty much gives you the power to control how your the appearance of your website. It goes hand to hand with HTML.
Here is an example of CSS:
h2 {
background-color: gray;
}
p {
text-align: center;
}
The h2 HTML tag I used earlier will now have the background color of gray and the p HTML tag will now be centered. This is how CSS and HTML coexist along each other. It can get a bit complix at times but its a lot of fun. I hope you learn something from my brief description of HTML and CSS.
Learn, Love, Code.


3.18. Solving Recurrence Relations (optional) (WORK IN PROGRESS)¶
3.18.1. Solving Recurrence Relations¶
Todo
- type: Equation cross-reference
Throughout this module, there are references to equations, both on this page and in the Summations module. These should be made into proper cross-references rather than hard-coded equation numbers.
Recurrence relations are often used to model the cost of recursive functions. For example, the standard Mergesort takes a list of size \(n\), splits it in half, performs Mergesort on each half, and finally merges the two sublists in \(n\) steps. The cost for this can be modeled as
In other words, the cost of the algorithm on input of size \(n\) is two times the cost for input of size \(n/2\) (due to the two recursive calls to Mergesort) plus \(n\) (the time to merge the sublists together again).
There are many approaches to solving recurrence relations, and we briefly consider three here. The first is an estimation technique: Guess the upper and lower bounds for the recurrence, use induction to prove the bounds, and tighten as required. The second approach is to expand the recurrence to convert it to a summation and then use summation techniques. The third approach is to take advantage of already proven theorems when the recurrence is of a suitable form. In particular, typical divide-and-conquer algorithms such as Mergesort yield recurrences of a form that fits a pattern for which we have a ready solution.
<IP_ADDRESS>. Estimating Upper and Lower Bounds¶
The first approach to solving recurrences is to guess the answer and then attempt to prove it correct. If a correct upper or lower bound estimate is given, an easy induction proof will verify this fact. If the proof is successful, then try to tighten the bound. If the induction proof fails, then loosen the bound and try again. Once the upper and lower bounds match, you are finished. This is a useful technique when you are only looking for asymptotic complexities. When seeking a precise closed-form solution (i.e., you seek the constants for the expression), this method will probably be too much work.
Example 3.19.1
Use the guessing technique to find the asymptotic bounds for Mergesort, whose running time is described by the equation
We begin by guessing that this recurrence has an upper bound in \(O(n^2)\). To be more precise, assume that
We prove this guess is correct by induction. In this proof, we assume that \(n\) is a power of two, to make the calculations easy. For the base case, \({\bf T}(2) = 1 \leq 2^2\). For the induction step, we need to show that \({\bf T}(n) \leq n^2\) implies that \({\bf T}(2n) \leq (2n)^2\) for \(n = 2^N, N \geq 1\). The induction hypothesis is
It follows that
which is what we wanted to prove. Thus, \({\bf T}(n)\) is in \(O(n^2)\).
Is \(O(n^2)\) a good estimate? In the next-to-last step we went from \(n^2 + 2n\) to the much larger \(4n^2\). This suggests that \(O(n^2)\) is a high estimate. If we guess something smaller, such as \({\bf T}(n) \leq cn\) for some constant \(c\), it should be clear that this cannot work because \(c 2 n = 2 c n\) and there is no room for the extra \(n\) cost to join the two pieces together. Thus, the true cost must be somewhere between \(cn\) and \(n^2\).
Let us now try \({\bf T}(n) \leq n \log n\). For the base case, the definition of the recurrence sets \({\bf T}(2) = 1 \leq (2 \cdot \log 2) = 2\). Assume (induction hypothesis) that \({\bf T}(n) \leq n \log n\). Then,
which is what we seek to prove. In similar fashion, we can prove that \({\bf T}(n)\) is in \(\Omega(n \log n)\). Thus, \({\bf T}(n)\) is also \(\Theta(n \log n)\).
Example 3.19.2
We know that the factorial function grows exponentially. How does it compare to \(2^n\)? To \(n^n\)? Do they all grow “equally fast” (in an asymptotic sense)? We can begin by looking at a few initial terms.
We can also look at these functions in terms of their recurrences.
At this point, our intuition should be telling us pretty clearly the relative growth rates of these three functions. But how do we prove formally which grows the fastest? And how do we decide if the differences are significant in an asymptotic sense, or just constant factor differences?
We can use logarithms to help us get an idea about the relative growth rates of these functions. Clearly, \(\log 2^n = n\). Equally clearly, \(\log n^n = n \log n\). We can easily see from this that \(2^n\) is \(o(n^n)\), that is, \(n^n\) grows asymptotically faster than \(2^n\).
How does \(n!\) fit into this? We can again take advantage of logarithms. Obviously \(n! \leq n^n\), so we know that \(\log n!\) is \(O(n \log n)\). But what about a lower bound for the factorial function? Consider the following.
Therefore
In other words, \(\log n!\) is in \(\Omega(n \log n)\). Thus, \(\log n! = \Theta(n \log n)\).
Note that this does not mean that \(n! = \Theta(n^n)\). Because \(\log n^2 = 2 \log n\), it follows that \(\log n = \Theta(\log n^2)\) but \(n \neq \Theta(n^2)\). The log function often works as a “flattener” when dealing with asymptotics. That is, whenever \(\log f(n)\) is in \(O(\log g(n))\) we know that \(f(n)\) is in \(O(g(n))\). But knowing that \(\log f(n) = \Theta(\log g(n))\) does not necessarily mean that \(f(n) = \Theta(g(n))\).
Example 3.19.3
What is the growth rate of the Fibonacci sequence? We define the Fibonacci sequence as \(f(n) = f(n-1) + f(n-2)\) for \(n \geq 2\); \(f(0) = f(1) = 1\).
In this case it is useful to compare the ratio of \(f(n)\) to \(f(n-1)\). The following table shows the first few values.
If we continue for more terms, the ratio appears to converge on a value slightly greater then 1.618. Assuming \(f(n)/f(n-1)\) really does converge to a fixed value as \(n\) grows, we can determine what that value must be.
for some value \(x\). This follows from the fact that \(f(n) = f(n-1) + f(n-2)\). We divide by \(f(n-2)\) to make the second term go away, and we also get something useful in the first term. Remember that the goal of such manipulations is to give us an equation that relates \(f(n)\) to something without recursive calls.
For large \(n\), we also observe that:
as \(n\) gets big. This comes from multiplying \(f(n)/f(n-2)\) by \(f(n-1)/f(n-1)\) and rearranging.
If \(x\) exists, then \(x^2 - x - 1 \rightarrow 0\). Using the quadratic equation, the only solution greater than one is
This expression also has the name \(\phi\). What does this say about the growth rate of the Fibonacci sequence? It is exponential, with \(f(n) = \Theta(\phi^n)\). More precisely, \(f(n)\) converges to
<IP_ADDRESS>. Expanding Recurrences¶
Estimating bounds is effective if you only need an approximation to the answer. More precise techniques are required to find an exact solution. One approach is called expanding the recurrence. In this method, the smaller terms on the right side of the equation are in turn replaced by their definition. This is the expanding step. These terms are again expanded, and so on, until a full series with no recurrence results. This yields a summation, and techniques for solving summations can then be used.
Example 3.19.4
Our next example models the cost of the algorithm to build a heap. You should recall that to build a heap, we first heapify the two subheaps, then push down the root to its proper position. The cost is:
Let us find a closed form solution for this recurrence. We can expand the recurrence a few times to see that
We can deduce from this expansion that this recurrence is equivalent to following summation and its derivation:
<IP_ADDRESS>. Divide-and-Conquer Recurrences¶
The third approach to solving recurrences is to take advantage of known theorems that provide the solution for classes of recurrences. Of particular practical use is a theorem that gives the answer for a class known as divide-and-conquer recurrences. These have the form
where \(a\), \(b\), \(c\), and \(k\) are constants. In general, this recurrence describes a problem of size \(n\) divided into \(a\) subproblems of size \(n/b\), while \(cn^k\) is the amount of work necessary to combine the partial solutions. Mergesort is an example of a divide and conquer algorithm, and its recurrence fits this form. So does binary search. We use the method of expanding recurrences to derive the general solution for any divide and conquer recurrence, assuming that \(n = b^m\).
Here is a more visual presentation of this same derivation.
So, we are left with this result:
At this point, it is useful to note that
This gives us
The summation part of this equation is a geometric series whose sum depends on the ratio \(r = b^k/a\). There are three cases.
\(r<1\). From Equation (4) of Module summation,
\[\sum_{i=0}^{m} r^i < 1/(1-r),\ {\rm a~constant.}\]Thus,
\[{\bf T}(n) = \Theta(a^m) = \Theta(n^{log_ba}).\]\(r=1\). Because \(r = b^k/a\), we know that \(a = b^k\). From the definition of logarithms it follows immediately that \(k = \log_b a\). Also note that since we defined \(n = b^m\), then \(m = \log_b n\). Thus,
\[\sum_{i=0}^{m} r^i = m + 1 = \log_bn + 1.\]Because \(a^m = n^{\log_b a} = n^k\), we have
\[{\bf T}(n) = \Theta(n^{\log_ba}\log_b n) = \Theta(n^k\log_b n).\]\(r>1\). From Equation (5) of Module summation,
\[\sum_{i=0}^{m} r^i = \frac{r^{m+1} - 1}{r - 1} = \Theta(r^m).\]Thus,
\[{\bf T}(n) = \Theta(a^mr^m) = \Theta(a^m(b^k/a)^m) = \Theta(b^{km}) = \Theta(n^k).\]
We can summarize the above derivation as the following theorem, sometimes referred to as the Master Theorem.
Theorem 3.19.1
The Master Theorem: For any recurrence relation of the form \({\bf T}(n) = a{\bf T}(n/b) + cn^k, {\bf T}(1) = c\), the following relationships hold.
This theorem may be applied whenever appropriate, rather than re-deriving the solution for the recurrence.
Example 3.19.5
Apply the Master Theorem to solve
Because \(a=3\), \(b=5\), \(c=8\), and \(k=2\), we find that \(3<5^2\). Applying case (3) of the theorem, \({\bf T}(n) = \Theta(n^2)\).
Example 3.19.6
Use the Master Theorem to solve the recurrence relation for Mergesort:
Because \(a=2\), \(b=2\), \(c=1\), and \(k=1\), we find that \(2 = 2^1\). Applying case (2) of the theorem, \({\bf T}(n) = \Theta(n \log n)\).
<IP_ADDRESS>. Average-Case Analysis of Quicksort¶
In Module Quicksort, we determined that the average-case analysis of Quicksort had the following recurrence:
The \(cn\) term is an upper bound on the findpivot and partition steps. This equation comes from assuming that the partitioning element is equally likely to occur in any position \(k\). It can be simplified by observing that the two recurrence terms \({\bf T}(k)\) and \({\bf T}(n - 1 - k)\) are equivalent, because one simply counts up from \(T(0)\) to \(T(n-1)\) while the other counts down from \(T(n-1)\) to \(T(0)\). This yields
This form is known as a recurrence with full history. The key to solving such a recurrence is to cancel out the summation terms. The shifting method for summations provides a way to do this. Multiply both sides by \(n\) and subtract the result from the formula for \(n{\bf T}(n+1)\):
Subtracting \(n{\bf T}(n)\) from both sides yields:
At this point, we have eliminated the summation and can now use our normal methods for solving recurrences to get a closed-form solution. Note that \(\frac{c(2n+1)}{n+1} < 2c\), so we can simplify the result. Expanding the recurrence, we get
for \({\cal H}_{n+1}\), the Harmonic Series. From Equation (10) of Module summation, \({\cal H}_{n+1} = \Theta(\log n)\), so the final solution is \(\Theta(n \log n)\).


Abstract.
Verification of concurrent data structures is one of the most challenging tasks in software verification.
The topic has received considerable attention over the course of the last decade.
Nevertheless, human-driven techniques remain cumbersome and notoriously difficult while automated approaches suffer from limited applicability.
The main obstacle for automation is the complexity of concurrent data structures.
This is particularly true in the absence of garbage collection.
The intricacy of lock-free memory management paired with the complexity of concurrent data structures makes automated verification prohibitive.
In this work we present a method for verifying concurrent data structures and their memory management separately.
We suggest two simpler verification tasks that
imply the correctness of the data structure.
The first task establishes an over-approximation of the reclamation behavior of the memory management.
The second task exploits this over-approximation to verify the data structure without the need to consider the implementation of the memory management itself.
To make the resulting verification tasks tractable for automated techniques, we establish a second result.
We show that a verification tool needs to consider only executions where a single memory location is reused.
We implemented our approach and were able to verify linearizability of Michael&Scott's queue and the DGLM queue for both hazard pointers and epoch-based reclamation.
To the best of our knowledge, we are the first to verify such implementations fully automatically.
CCS Concepts: • Theory of computation → Data structures design and analysis; Program verification; Shared memory algorithms; Program specifications; Program analysis;
Additional Key Words and Phrases: static analysis, lock-free data structures, verification, linearizability, safe memory reclamation, memory management
ACM Reference Format:
Roland Meyer and Sebastian Wolff. 2019. Decoupling Lock-Free Data Structures from Memory Reclamation for Static Analysis. Proc. ACM Program. Lang. 3, POPL, Article 58 (January 2019), 31 pages. https://doi.org/10.1145/3290371
Our paper presents an analysis for verifying lock-free data structures that use safe memory reclamation (SMR) techniques. We follow a compositional approach which factors out the verification of the SMR implementation. Consequently, we have two distinct tools for:
The SMR specification is given in form of an observer automata (hard coded into our tools). For data structures, we verify liniearizability (we assume that programs are annotated with linearization points).
We submitted our tool to the POPL'19 artifact evaluation where it received the Artifact Evaluated -- Reusable badge.
In the this page we discuss how to reproduce our experiments. Therefore, we walk through the installation, compilation, and benchmarking. In the end, we briefly link the concepts and techniques from the paper to our implementation.
Our tools do not come with a front end (aka parser). To analyse programs not included in our benchmarks, one has to compile an appropriate binary first. If desired, consider the provided benchmark implementations. For example, consider:
TMRexp-POPL19/test/HP/MichaelScottQueue.cpp
, orTMRexp-POPL19/test/HP/Stack.cpp
.TMRexp-POPL19/src/prog.hpp
, lines 655f).
This section describes how to setup your system to repeat the benchmarks from the paper.
~/Desktop/pw.txt
).
The artifact is located at ~/popl19artifact/
.
The folder ~/popl19artifact/Binaries
contains executables corresponding to the benchmarks from the paper.
If you choose this option you can skip the remainder of this section.
The source code can be downloaded from GitHub here:
For a unified description of the installation/compilation for both tools, we assume that unzipping yields a folder named TMRexp-POPL19
.
To compile this project you need CMake, a C++17 compatible compiler, and Boost multi_array. Compilation was tested with Apple LLVM v.9.1.0, Apple LLVM v.10.0.0, Clang v.5.0, and Clang v.6.0.
To build the project, simply type make in the root directory of the downloaded sources.
cd path/to/TMRexp-POPL19
make
This creates a folder build/bin
containing all executables.
Alternatively, you can do the following (for example, to specify the compiler to be used):
mkdir build
cd build
cmake .. -DCMAKE_CXX_COMPILER=/path/to/CXX-compiler
make
Again, folder build/bin
contains all executables.
We describe how to repeat the benchmarks for verifying lock-free data structures relative to an SMR implementation from the paper.
~/popl19artifact/Binaries/<Program>_<SMR>
to run the benchmark for Program
using SMR
.
When compiling on your own, execute TMRexp-POPL19/build/bin/<Program>_<SMR>
(for the DGLM Queue see the discussion below).
We evaluated our tool on a Coarse Stack, a Coarse Queue, Treiber's Stack, Michael&Scott's Queue, and the DGLM queue using no SMR (N
), No Reclamation/Garbage Collection (G
), Hazard Pointers (H
), and Epoch-Based Reclamation (E
).
C-style pseudo code is given in the following.
We mark lines that are required only for a specific SMR by the aforementioned letters N
, G
, H
, and E
.
To run the benchmarks got to the build/bin/
folder and execute the corresponding binary.
The naming scheme is <DS>_<SMR>
where <DS>
is the name of the benchmark program and <SMR>
is the reclamation scheme.
For example, to benchmark the running example from the paper, Michael&Scott's Queue using Hazard Pointers (HP), you have to do the following:
cd path/to/TMRexp-POPL19/build/bin
./MichaelScottQueue_HP
As stated in the paper, the implemented shape abstraction requires hints to verify the DGLM Queue.
To enable/disable hinting you have to set the corresponding flag in src/config.hpp
and recompile the tool.
More precisely, you have to change line 22 from
#define DGLM_HINT false
to
#define DGLM_HINT true
Beware: using DGLM_HINT=true
with any benchmark other than the DGLM Queue exhibits undefined behavior!
For users of the VM image: the folder ~/popl19artifact/Binaries/
already contains the properly compiled binaries.
The binaries where compiled from ~/popl19artifact/chkds/
and ~/popl19artifact/chkds-DGLM/
for all benchmarks except the DGLM Queue and the DGLM Queue, respectively.
As reported in the paper, running the benchmarks on an Intel Xeon<EMAIL_ADDRESS>with Ubuntu 16.04 and using Clang version 5.0 we expect the following running times and verification results.
| Program | SMR | Time Verif. | States | ABAs | Time ABA | Linearizable |
|---|---|---|---|---|---|---|
| Coarse Stack | GC | 0.44s | 300 | 0 | 0s | yes |
| None | 0.5s | 300 | 0 | 0s | yes | |
| Coarse Queue | GC | 1.7s | 300 | 0 | 0s | yes |
| None | 1.7s | 300 | 0 | 0s | yes | |
| Treiber's Stack | GC | 3.2s | 806 | 0 | 0s | yes |
| EBR | 16s | 1822 | 0 | 0s | yes | |
| HP | 19s | 2606 | 186 | 0.06s | yes | |
| Opt. Treiber's Stack | HP | 0.8s | - | - | - | no* |
| Michael&Scott's Queue | GC | 414s | 2202 | 0 | 0s | yes |
| EBR | 2630s | 7613 | 0 | 0s | yes | |
| HP | 7075s | 19028 | 536 | 0.9s | yes | |
| DGLM Queue | GC | 714s | 9934 | 0 | 0s | yes** |
| EBR | 3754s | 27132 | 0 | 0s | yes** | |
| HP | 7010s | 41753 | 2824 | 26s | yes** |
* Pointer Race due to an ABA in push
makes the verification fail.
** Imprecision in the heap abstraction required hinting that Head
cannot overtake Tail
by more than one node.
We describe how to repeat the benchmarks for verifying SMR implementations from the paper.
~/popl19artifact/Binaries/<SMR>
to run the benchmark for the SMR implementation SMR
.
When compiling on your own, execute TMRexp-POPL19/build/bin/<SMR>
.
We evaluated our tool on an Hazard Pointer (HP) and an Epoch-based Reclamation (EBR) implementation both of which support dynamic joining/parting of threads. C-style pseudo code is given in the following.
To run the benchmarks got to the build/bin/
folder and execute the corresponding binary.
The naming scheme is <SMR>_<Info>
where <SMR>
is the (abbreviated) name of the benchmark program and <Info>
is a description of the implementation (we have various implementations for each class).
For example, to benchmark the running example from the paper, the Hazard Pointer implementation, you have to do the following:
cd path/to/TMRexp-POPL19/build/bin
./HPimpl
As reported in the paper, running the benchmarks on an Intel Xeon<EMAIL_ADDRESS>with Ubuntu 16.04 and using Clang version 5.0 we expect the following running times and verification results.
| Program | Observer | Time | States | Correct |
|---|---|---|---|---|
| Hazard Pointers | OBase x OHP | 1.5s | 5437 | yes |
| Epoch-based Reclamation | OBase x OEBR | 11.2s | 11528 | yes |
When executing a binary from above, our tool prints the following:
For an example, the output of chsmr HPimpl
has the following form:
post image... [#enc] done! [#enc=0.9k, #step=0k, #steptotal=0k]
interference... [32 buckets][#bucketsize][198][129][130][129][4][59][59][59][105][105][70][70][4][59][59][59][59][59][17][17][105][105][59][59][101][37][70][70][17][17][37][67] done! [#enc=2.2k, #step=85k, #steptotal=40k]
post image... [#enc][2k][3k][4k][4k] done! [#enc=5.0k, #step=4k, #steptotal=5k]
interference... [32 buckets][#bucketsize][274][253][255][253][79][156][156][156][223][223][157][159][79][156][156][156][154][154][93][95][223][223][154][154][217][107][157][157][93][93][105][153] done! [#enc=5.2k, #step=172k, #steptotal=96k]
post image... [#enc] done! [#enc=5.4k, #step=0k, #steptotal=5k]
interference... [32 buckets][#bucketsize][274][253][255][253][156][156][156][156][223][223][159][159][156][156][156][156][154][154][95][95][223][223][154][154][217][135][157][157][93][93][133][153] done! [#enc=5.4k, #step=173k, #steptotal=151k]
post image... [#enc] done! [#enc=5.4k, #step=0k, #steptotal=5k]
interference... [32 buckets][#bucketsize][274][253][255][253][156][156][156][156][223][223][159][159][156][156][156][156][154][154][95][95][223][223][154][154][217][135][157][157][93][93][133][153] done! [#enc=5.4k, #step=173k, #steptotal=207k]
The output tells you that sequential steps (post image...
) and interference steps (interference...
) are executed in rounds.
Sequential steps print the current size of the fixed point in regular intervals.
For example, in the third line we have [#enc][2k]
meaning that there are 2000 views at the time of the output.
Interference steps print the number of buckets.
The explored views are stored in buckets to reduce the search space of interference steps.
Views from different buckets are guaranteed to not match, i.e., are guaranteed to not require interference.
In the second line, for example, we have [32 buckets][#bucketsize][274]
.
This states that there are 32 different buckets and that the first bucket contains 274 views.
The remaining output is straight forward.
The following tables relate (informal) descriptions of the implemented analysis from the paper to the implementation.
| Paper | Implementation | Description |
|---|---|---|
| Views | src/cfg.hpp |
Views are implemented by the class Cfg .
They carry, among other things, a shape abstraction of the memory, validity information, and observer states.
|
| Thread-modular fixed point | src/fixpoint.cpp |
The fixed point computation maintains a collection of views the post image of which may not have been explored.
The post image of these views is computed and added to the fixed point.
The implementation proceeds in rounds.
In each round sequential steps are performed exhaustively first and then interference steps are applied.
(There is an alternative fixed point computation using a work list approach. It can be activated by setting the WORKLIST_INTERFERENCE to true in the configuration file.)
|
| Shape abstraction | src/shape.hpp |
Class Shape implements a container for a shape abstraction of a specific memory layout.
More details on the shape abstraction can be found in Abdulla et al. [2013,2017].
|
src/post/*.cpp |
Contains post-image computation for the shape abstraction for every supported statement type. | |
| Interference | src/fixp/interference.cpp |
Implements interference steps. Such a step considers all pairs of previously explored views, combines them into a two-thread view, computes a post image for one of the threads, and projects the result to the other thread. The resulting views are added to the fixed point. |
| Observers | src/observer.hpp |
Class Observer implements observer automata as presented in the paper.
|
test/ObserverFactory.hpp |
Creates observer instances along the lines of the paper. |
| Paper | Implementation | Description |
|---|---|---|
| Views | src/cfg.hpp |
Besides the above, also stores freedness information of the single reusable cell. |
| Elision support | test/ObserverFactory.hpp |
The implementation relies on Lemma 6.1, thus does not check if the observer supports elision (Definition 5.14). |
Environment free |
src/post/mem.cpp |
Following the semantics for environment frees, rule (Free), the implementation checks which frees can be executed by checking whether the observer reaches a final state upon consuming a free event. |
| Reallocation of a single address | src/post/mem.cpp |
To identify the single address available for reuse, shapes carry a special ghost pointer to the reusable cell. Moreover, views carry a flag stating whether or not the cell is freed. If so, an allocation can yield a pointer to that cell. Otherwise, the allocation can only yield fresh cells. |
| Validity | src/cfg.hpp |
Views (class Cfg ) carry validity information about pointers.
|
src/post/*.cpp |
The post image operator updates the validity according to the definition in the paper. | |
| Pointer race check | src/post.cpp |
The post image operators check whether an unsafe access or a racy SMR call is performed.
The latter relies on Lemma 6.2 and deems racy calls to retire that use an invalid pointer.
|
| Harmful ABA check | src/chkaware.cpp |
Checks for every view where an invalid pointer can be compared in an assert for harmful ABAs.
The implementation follows the description in the paper.
|
| Paper | Implementation | Description |
|---|---|---|
| Views | src/cfg.hpp |
Besides the above, also stores data (set) abstractions. |
| Retain records | src/shape.hpp |
Stores the myRecord pointer of a non-view thread.
|
Last retire |
test/ObserverFactory.hpp |
Introduces redundant observer locations to judge whether or not the observed thread performed the last retire call.
|
src/fixp/interference.cpp |
Prunes interference among views for identical threads. | |
| Data (set) abstraction | src/post/*.cpp |
Contains post-image computation for the data abstraction for every supported statement type. |


An R package with tools to help write and maintain other OHDSI R packages. Other OHDSI R packages should not depend on or import OhdsiRTools.
# Create renv lock file
OhdsiRTools::createRenvLockFile(rootPackage = "MyStudyPackage",
includeRootPackage = TRUE)
# Identify problems in R code in a package:
checkUsagePackage("OhdsiRTools")
install.packages("remotes")
remotes::install_github("ohdsi/OhdsiRTools")
Documentation can be found on the package website.
PDF versions of the documentation are also available: * Package manual: OhdsiRTools.pdf
Read here how you can contribute to this package.


Please complete the form below. Your information will only be saved once you click the Save & Continue button at the end of the page.
An Authorized Owner of Controlled Equipment includes a person who is authorized under an enactment of BC or Canada to manufacture a drug or natural health product.
What enactment authorizes you to manufacture these products? Please select all the options that apply.
Food and Drug ActWhat kind of licence do you possess that authorizes you to manufacture a drug or natural health product? Please select all the options that apply.
DrugsWhat kind of licence do you possess that authorizes you to manufacture a drug or natural health product? Please select all the options that apply.
Drug Establishment Licence


Usage¶
A bunch of examples of the different features of the package. Refer to the documentation to get a better view of each function arguments.
Blocks¶
A block is a function tagged with the decorator called (guess what) block
.
from vispipe import block
@block
def identity_block(x):
return x
Or a class with a run
method.
@block
class identity_class_block:
def __init__(self):
# you can have attributes stored and used by run method
self.useless_value = 42
pass
def run(self, x):
return x
A block can have multiple inputs.
@block
def add(x, y):
return x + y
# Or none
@block
def just_a_one():
return 1
All the inputs we defined right now are ‘real’ inputs and will be filled by connecting the block to other blocks of the pipeline. We may want to have static arguments as well, an input will become a static argument once we assign a default value to it. If you want to use the visualization you should also specify the type so that they can be parsed correctly.
@block
def add_constant(x, k: int = 42):
# x will be a 'real' input while k will be a static argument
return x + k
Now that you know how blocks work let’s see how to create a pipeline, add and connect them.
Pipeline Building¶
from vispipe import Pipeline
# Create a pipeline
p = Pipeline()
# Add nodes by name
ones = p.add_node('just_a_one')
adder = p.add_node('add_constant', k = 10) # We can specify the value of static arguments during add_node
# The add_node function will return the unique identifier for the node, it is an integer and
# corresponds to the hash of the node, you will use it to interact with the node.
# Connect nodes
# syntax: add_conn(from_hash, output_index, to_hash, input_index)
p.add_conn(ones, 0, adder, 0)
# We have a working pipeline now! Let's start it
p.run()
# We can wait for it to end using
p.join(timeout=1) # It supports timeout argument similarly to Threading std library
# In this case the pipeline will run indefinitely and we have not way to interact with it.
# Let's Add an output to it
p.add_output(adder)
# If we now run it we can iterate over the outputs of adder
p.run()
for x in p.outputs[adder]:
print(x)
>>> 11 # It will add 10 that is our constant to 1 which is the just_a_one output.
# (...)
>>> 11 # It will run indefinitely as there's no ending.
Saving and reloading¶
# Once we are happy with our pipeline we can save it to pickle
p.save(file_path)
# And reload it in a later stage
p = Pipeline()
p.load(file_path)
# Or more concisely
p = Pipeline(path=file_path)
Advanced Block creation¶
Pipeline._empty
and Pipeline.skip
objecs¶
You may have noticed that the flexibility of the blocks we created is pretty limited, we need to return a value at each call and we will always receive an input. To overcome this there are two particular objects that get treated in a particular way:
Pipeline._empty
allows to specify that we do not want to return any result yet.
# The example is based on the benchmark block from ops/utils.py
@block
class benchmark:
def __init__(self):
self.n = 1000
self.start_time = None
def run(self, x):
if self.start_time is None:
self.start_time = time.time()
self.n -= 1
if self.n == -1: # After 1000 iterations we return delta time
delta = time.time() - self.start_time
return delta
# (...) missing code to manage the ending
return Pipeline._empty # Otherwise we are not ready to return an output
Pipeline._skip(value)
allows to return a value while also skipping the next input.
This is particularly useful when you need to iterate over an input.
# The example is based on iterator from ops/flows.py
@block
class iterator:
def __init__(self):
self.iterator = None
def run(self, x):
if self.iterator is None:
self.iterator = iter(x)
try:
# As we can still iterate we return a skip object containing the next value
y = Pipeline._skip(next(self.iterator))
except StopIteration:
# If we finished the iterator we return an empty so that we can wait for next input
self.iterator = None
y = Pipeline._empty
return y
Macro Blocks¶
Macro blocks are a convenient way to speed up a set of linearly connected blocks. Blocks that are part of a macro will be run together (instead of connected with queues). While this limits the flexibility of a part of the pipeline the functions will run a lot faster as they completely skip the communication overhead. (Please refer to documentation for a better explanation of this functionality)
# (...)
p.add_macro(start_hash, end_hash) # Will add a macro from start hash to end hash.
p.remove_macro(node_hash) # Will delete the macro the node belongs to.
An example¶
Loads the mnist dataset from a numpy array + the labels associated.
It then reshape the images to be actual (28, 28)
, resize them to another resolution
and creates batches from them.
# Create pipeline
p = Pipeline()
# Create nodes
load_images = p.add_node('np_iter_file', path='tests/data/mnist.npy')
load_labels = p.add_node('np_iter_file', path='tests/data/mnist_labels.npy')
reshape = p.add_node('np_reshape', shape=(28, 28))
resize = p.add_node('resize_cv2', width=56, height=56)
batch_images = p.add_node('batchify/images', size=32)
batch_labels = p.add_node('batchify/labels', size=32)
# Add connections
p.add_conn(load_images, 0, reshape, 0)
p.add_conn(reshape, 0, resize, 0)
p.add_conn(resize, 0, batch_images, 0)
p.add_conn(load_labels, 0, batch_labels, 0)
# Set outputs
p.add_output(batch_images)
p.add_output(batch_labels)
# Run it
p.run(slow=False, use_mp=False)
for batch_x, batch_y in zip(p.outputs['images'], p.outputs['labels']):
print(batch_x.shape, batch_y.shape)