Friday, April 12, 2019

Concurrency in Rust programming language- PART1

rust concurrency

Concurrency in Rust - PART 1

As per Rust documentation, concurrency in Rust is Fearless concurrency. Handling concurrency in a safe and efficient way is one of the Rust goal. The Ownership is the back bone of rust concurrency.

Concurrency means multiple computations at the same time.

  • In fact, concurrency is essential part of modern programming

eg > websites should handle multiple users at the same time
Graphical user interface need to do some background work when users are not interrupting the screens.
Multiple applications needs to run on the cloud (server)
Travel reservation system
Many algorithms can be broken down to concurrent parts -
merge sort
quick sort
summing a list by summing fragments in parallel

Concurrency can be achieved in Hardware level and software level. Here we will be talking about software concurrency and what makes Rust an efficient programming language to handle this.

Hardware examples:

  • A single processor can have multiple execution pipelines (but only one set of registers)
  • A processor can have multiple cores (multicore)
  • A computer can have multiple processors
  • A network can have multiple computers (Grid computing happens on these)
  • An internet has multiple networks
  • All combinations of the above

Software examples:

  • Multiprogramming, or running a lot of programs concurrently (the O.S. has to multiplex their execution on available processors). For example:
    • downloading a file
    • listening to streaming audio
    • having a clock running
    • chatting
    • analyzing data from some weird experiment
    • streaming a movie

Two Models for Concurrent Programming

  • Shared Memory - In this case, the same memory will be shared amount the processors /threads or programs.
    A and B programs can be trying to use the same object .
    A and B threads can be using the same file system that they can read and write. etc…
  • Message passing -
    There will be a transmitter and a receiver in this model. They communicate each other through a communication channel. Modules sends the messages and the incoming messages will be queued up for modules.
    A web browser and web server communication is an example. Web browser client request for a connection and web page, the server sends the data back to browser.

Jumping directly into Rust concurrency

Process. A process is an instance of a running program that is isolated from other processes on the same machine. In particular, it has its own private section of the machine’s memory.
Thread. A thread is a locus of control inside a running program. Think of it as a place in the program that is being run, plus the stack of method calls that led to that place to which it will be necessary to return through.
Threads are automatically ready for shared memory, because threads share all the memory in the process. It needs special effort to get “thread-local” memory that’s private to a single thread. It’s also necessary to set up message-passing explicitly, by creating and using queue data structures.

use::std::thread;

fn main() {

// spawning a new thread
    let handle = thread::spawn(||{
        loop {
                println!("thread1");
        }
    });

//looping the main thread
    loop{
        println!("thread2");
    }


}

thread::spawn function creates the new thread and returns a handle to it. The parameter would be a closure . Here it is an infinite loop that prints thread1.
You will see thread1 and thread2 printing in the screen. Unfortunately I could not get thread2 in the screenshot!

Thread 1 and Thread 2

For listing the threads running under the process, you can use below command in linux
get the process id using command
ps -e
then use top -H -p processid
The memory and CPU usage for each threads can be listed using above command.

threads in linux Rust programming

Run the below code and see the output …
The program just print “hello world”. It will not wait for the inner thread to complete and print the vector.

use::std::thread;
fn main() {
    let v = vec![1,2,3];
    let handle = thread::spawn(||{
                println!("{:?}",v);
    });
//    handle.join().unwrap();
    println!("Hello, world!");
}

Now remove comments (//) from handle.join().unwrap(); and run the program. You would assume the main thread wait for the inner thread to print the vector values as handle.join() makes main thread to wait/join with inner thread.

But,
We do get a compile time error . The error says the variable vector “v” does not live long enough. If the main thread complete without waiting for inner thread to complete (as we are seen above). The borrowed vector points to wrong memory when its tries to execute. Here Rust help us.

Rust compiler caught that scenario and threw an error .

   Compiling concurrent-proj2 v0.1.0 (/home/naveen/rustprojects/concurrent-proj2)
error[E0597]: `v` does not live long enough                                                                                                    
  --> src/main.rs:11:19                                                                                                                        
   |                                                                                                                                           
10 |     let handle = thread::spawn(||{                                                                                                        
   |                                -- value captured here                                                                                     
11 |         println!("{:?}",v);                                                                                                               
   |                         ^ borrowed value does not live long enough                                                                        
...                                                                                                                                            
16 | }                                                                                                                                         
   | - `v` dropped here while still borrowed

We can use the move keyword to transfer the ownership of the variables that we are going to use in the inner thread from the environment.

Below program prints both vector values and helloworld.

use::std::thread;
fn main() {
    let v = vec![1,2,3];
    let handle = thread::spawn(move ||{
                println!("{:?}",v);
    });

   handle.join().unwrap();
    println!("Hello, world!");
}
    

Threads Flow diagram

vector 'v'
handle
main thread
inner thread
main thread
handle.join - wait for the inner thread to finish
main thread get completed

Wednesday, March 13, 2019

Have you heard about Competitive programming ?

---

Competitive Programming

If you are looking for job in Google,Amazon or facebook as programmer or developer/designer, definitely you will be familiar with the word "Competitive programming ".

I thought of sharing some of my thoughts on "competitive programming ".
As per wikipedia - Competitive programming is a mind sport usually held over the Internet or a local network. https://en.wikipedia.org/wiki/Competitive_programming

As per definition it’s a “sports”

I heard about hackerrank 3 or 4 years back. I got surprised seeing the success of hackerrank. Definitely its very useful website those who are trying to understand different algorithms/concepts/problems in computer science. After that there was a rain of similar websites … Codechef, CodeByte etc …etc … I don’t know which one of these came first.

But I would suggest nothing harm in login those websites and try to solve some of the problems . Don’t get disappointed /discouraged if you are not able to solve the questions. you don’t need to be a competitive programmer to be a programmer.

I am not huge fan of competitive programming. But it improves your programming skill in multiple perspective and definitely you might need to have this skill for getting into Product based Software companies like Google, Amazon and facebook etc . When I started trying to solve some of the problems in code force , I thought I would require PHD in mathematics to understand the problems . Most of them will be really tough mathematical problems. But if you start from easy , medium and then to difficult once, I hope you won’t need to run away from it :-)

Let me start with advantages of Competitive programming

  • You are going to get good understanding on the Algorithms and data structures .

  • You will get to know different areas in computer science - number theory,set theory,graph theory,string analysis etc. If you ask me , Are these mathematics subjects? I would need to say “YES”. But the fact is you need to have good understanding on these areas in order to develop something unique. ( This is debatable subject) , you can develop innovative or useful applications without much deep understanding on these areas.

  • definitely it’s a plus point for you to get into Software companies.

  • This gives you the ability to approach problems in different ways and helps to get the optimized one.

  • Definitely you will come to time complexity O(n) and space complexity in computer programming :-)

  • Some of the competitive programming sites gives you only limited time to solve the problem. When you start solving the problems in time bound question ,this helps a lot in interviews. You will be able to face the software companies interviews more efficiently.

I think I wrote some advantages , so let me mention some of the websites you can try this .

In my opinion you don’t need to be competitive programmer to become a programmer/developer.

Competitive programming Drawbacks:

  • First of all , its not a technology or programming style or skill that every programmer is needed. Everybody know we need good algorithms to perform the program well. Reading,writing,debugging programs will makes you skillful programmer. Sometimes competitiveness makes to take decision immediately or jump into conclusion quickly.

  • For getting into competitive programming there are some prerequisites - good mathematical knowledge, Computer languages that the websites are using, good knowledge in computer science concepts.

  • If you are trying to learn a programming language from basics (eg: C programming ), I don’t think those sites are the starting point. Those who are good in C, C++,python etc languages , these websites will be a good place to play around.

  • Competitive programming will not take you to most of the computer applications areas .
    eg: Those who are interested in embedded systems , will not get any knowledge on peripheral or architecture of the micro controller/processor from this. or those who are all interested website designing and development not going to get much from competitive programming apart from understanding on the algorithms or logical thinking.

  • Nowadays Application building is like “building blocks” game. More you know about libraries and modules on the area, you will be succeeded in building some good applications.

  • Software life cycle is totally different - As you know it start with requirement gathering,designing,coding,unit testing, functional testing and User acceptance testing and deployment etc. I don’t see competitive programming give much importance to designing and collaboration and testing.

  • If you look at object oriented programming or functional programming , they are a programming style that every programmer should be aware of .

  • You can build innovative applications without competitive programming skills.

Conclusion

Please don’t consider Competitive programming as waste of time. It will definitely improve knowledge on algorithms and computer theories. Keep improving your programming skill on competitive perspective as well. Also be ware of that there are lot of other areas in programming where we can focus on application building or we can playground. As I said earlier You don’t need to be competitive programmer to be developer/programmer.

Please share your thoughts and comments. Thanks!

Tuesday, March 12, 2019

Rust Iterators

iterators

Iterators in Rust programming

Nowadays Iterators are every programmer’s tool in hand.When I program array of objects/strings in C programming , I always wish that I could have some tool/function/operator where we can iterate through these objects or strings(words). “for” loop or “while” loop are going through array index in C programming .

If you are storing words in Array it become 2 dimensional array. So iterating through “words” become even more difficult in C programming .But it will be convenient if you can iterate through the types values/objects in the array. eg: Array(“I”,“like”,“rust”,“programming”) …if you can just iterate through the words rather than reading through the letters, it will be easy to make the words manipulations.

It is Functional programming style where we can just tell the program to iterate through the specified type .
Another use case would be eg: In the given Array (2,4,6,8) of elements if we want to find cube for all the elements in the array and then filter if cube is even number.

For conventional Loop structure we will be iterating through each element and find cube then check and filter if it is even. How great it would be if we can have something like below give us the same output number/maths calculations

example: array.iter().filter(x/2==0).collect()

eg2: words or sentence manipulation

array.iter().filter( words_contains_vowels)

It improves the readability of the program a lot. This functional programming style improves the readability ,but at the same time we can’t compromise the performance . Since they are as fast as our native loops , they are “Zero cost abstraction” in Rust ## iter from standard library The standard library std::iter provides Trait is Iterator. You want to build iterator any Struct ,

you can implement Iterator on your collection with below trait

trait Iterator { type Item fn next(&mut self) ->Option(Self::Item); }

In the below example, suppose if I have an input stream coming from outside and I want to iterator over word by word

//the structure which store the words and index of the words
//note :Since we are using String slice reference , the life time needs to provided explicitly 

struct Mystream<'a>{
    words: Vec<&'a str>,
    index:usize
}

//implementing the structure with methods "new" and "next_word"
//"new" method create a structure object with words generated from  stream
//next_word method calls next method in the Iterator trait

impl <'a>Mystream<'a>{

//"new" method get the string and split them into words vector
//index will be zero for object, but we will increment it in each iteration and use it as indexing the vector
    fn new(stream:&'a str) -> Mystream{
        Mystream{
             words : stream.split(' ').collect(),
             index:0,
        }
    }

//next_word method calls the "next" method from the iterator trait    
    
    fn next_word(&mut self) ->Option<&'a str>{
            self.next()
    }

}

//standard implementation for Iterator for "Mystream" struct

impl <'a>Iterator for Mystream<'a>{
    type Item = &'a str;
    
    fn next(&mut self) -> Option<&'a str>{
            self.index +=1;
            match Some(self.words[self.index]){
                Some(word) => Some(word),
                None => None,
            }
    }
}



fn main(){
    
    let mut mystream = Mystream::new("I like to implement Rust Iterator for my stream");
    let mut len = mystream.words.len();
    println!("{:?},{}",mystream.words[0],len);
    len = len -1;
    while len > 0 {
    
         println!("{:?},{}",mystream.next_word().unwrap(),len);
         len = len -1;
    }
    
}

Not sure above example is tough one, but let me try to explain it… Let assume we have a stream of words coming from input port, our task is to store it in a struct as words .(ie: split the sentence into words). I tried to explain most of the things in the comment section. But still we will go through it … The implementation of Iterator for “Mystream” struct is important part in the code. For understanding Iterator implementation you should know what is trait and struct creation and implementation of struct in rust

Iterator

If look at the Iterator trait documentation, they ask us to create an associated type Item (Associated types are a way of associating a type placeholder with a trait such that the trait method definitions can use these placeholder types in their signatures.) and required method “next

The next method passing parameter and return parameters are mentioned in the example.

As a general rule , for any Trait Rust documentation you will get the required methods or associated types needs to implemented for using it for your struct. Also we need to implement that Trait for our struct.
This case,

impl <'a>Iterator for Mystream<'a>

Since we are using vector of string slice(a reference type), we need to provide life time for it and struct.

Here we have given the associated type Item as &'a str (string slice) which means we are planning to iterate through string slice when the next method calls.

Return type for next method is Option <Self:Item> which means we need use match keyword to return Some(word) if there is value and None if nothing.

In the case Collection types: we can use the
Array,Vec, Hash etc with iter metod.



use std::collections::HashMap;

fn main(){
    let arr = [1,2,3];
    let v = vec![4,5,6];
    let mut h = HashMap::new();
    h.insert(1,"naveen");
    h.insert(2,"davis");
    h.insert(3,"tom");
    println!("{:?}",arr.iter());
    
    for i in arr.iter(){
        println!("{}",i);
    }
    
    for i in v.iter(){
        println!("{}",i);
    }
    
    for (i,name) in h.iter(){
        println!("{:?}",name);
    }
    
    println!("{:?}",arr.iter().next()); //this is going print only first element
    println!("{:?}",arr.iter().next()); //this is going print only first element
    println!("{:?}",arr.iter().next()); //this is going print only first element
    println!("{:?}",arr.iter().next()); //this is going print only first element
    
    println!("{:?}",h.iter().next());  //this is going print only first element
    println!("{:?}",h.iter().next());  //this is going print only first element
    println!("{:?}",h.iter().next());  //this is going print only first element
    println!("{:?}",h.iter().next());  //this is going print only first element
}
iterator_cont

Iter

We can iterate through collection in 3 ways

  • iter(), which iterates over &T.
  • iter_mut(), which iterates over &mut T.
  • into_iter(), which iterates over T.

iterate through immutable reference , in this case we are not supposed to change the value and but we using only reference to value

Rule one: any borrow must last for a scope no greater than that of the owner
Rule two: you may have EITHER 1+ immutable borrows OR EXACTLY 1 mutable borrow

What happens when we compile this code ?
If you have already gone through some Rust program before, you will shout immediately  "compile time" error. As the vector moved in the first for loop and ownership has transfered, so when you try to use it again in the main the value was already dropped. We can use reference to the values to avoid this problem.

True . Rust won't allow to 
fn main() {
   
   let v = vec![3,4,5,7];
   
   for i in v {
      
            println!("{:?}",i);
   }
   
   for i in v {
       println!("{}",i);
   }
   
}

```rust_errors
use of moved value: `v`
  --> src/main.rs:10:13
   |
5  |    for i in v {
   |             - value moved here
...
10 |    for i in v {
   |             ^ value used here after move

In the below example , we solve above problem passing reference to for loop,
You can either use v.iter() or &v


fn main() {
   
   let v = vec![3,4,5,7];
   
   for i in &v {
      
            println!("{:?}",i);
   }
   
   for i in v.iter() {
       println!("{}",i);
   }
   
   println!("{:?}",v);
   
}

If you really want to pass the ownership to the for loop,
use either v or v.into_iter()


fn main() {
   
   let v = vec![3,4,5,7];

   for i in v.into_iter() {
       println!("{}",i);
   }
   
   println!("{:?}",v);
   
}
```rust_errors
 for i in v.into_iter() {
   |             - value moved here
...
11 |    println!("{:?}",v);
   |                    ^ value borrowed here after move
   |
   = note: move occurs because `v` has type `std::vec::Vec<i32>`

Another scenario is you want to update or change the value inside the for loop
you can either pass &mut v or you can use v.iter_mut()

fn main() {
   
   let mut v = vec![3,4,5,7];
   
   for i in &mut v {
      
        *i +=1;
       println!("{:?}",i);
   }
   
   println!("\nsecond iteration to change values\n");
   for i in v.iter_mut() {
      
        *i +=1;
       println!("{:?}",i);
   }
   
   println!("{:?}",v);
   
}

IntoIterator

If you want to use ’ for’ loop in your type, you will need to build the trait IntoIterator for the type.

We will see how to implement an IntoIterator for our type.

IntoIterator

Let build a ‘for’ loop for your Struct

How nice it would be if you can do a for loop which iterate through

[derive(Debug)]
struct Sentence{
    words: Vec<String>,
}

impl IntoIterator for Sentence {
    type Item = String;
    type IntoIter = std::vec::IntoIter<std::string::String>;
    fn into_iter(self) -> Self::IntoIter {
        self.words.into_iter()
    }
}


fn main() {

    let sentence = Sentence { 
        words: vec!["one".to_string(), "two".to_string()]
    };
    
    for word in sentence{
        println!("{}",word.contains("w"))
    }
   
}
Standard Output
false
true

In the above example we are creating Sentence Struct which our type. In that we are storing words as Vector elements.

As we discussed in IntoIterator trait implementation, we need to implement the trait for our type Sentence

So two associated types are required ,

one is Item which is the item we are iterating through.
second is IntoIter ie in which type we are iterating through. here it is std::vec::IntoIterstd::string::String

Note: if it were a vector of integers , it would be std::vec::IntoIter

The required method for IntoIterator trait is into_iter which is also implemented with Rust document mentioned parameter and return type.