Help for my parallel sum

Thanks a lot, I’ll take a look tomorrow as it’s late here now.

But you’re using an external crate :wink:

In Rust, std primarily contains functionality that requires special support in the compiler. Functionality that does not require special support typically is developed in other crates.

Because of Rust’s guarantees of backward compatibility it is very difficult to improve functionality in std, whereas functionality in other crates can be improved through semver without breaking Rust’s guarantees. That is one reason why Rust is not a “batteries included” language, because it’s almost impossible to replace defective batteries if they are in std.

12 Likes

@TomP Thanks for your explanation.

So does this mean that what I try do achieve is impossible without resorting to an external crate or duplicating what this external crate is providing?

Let me play the devil’s advocate. Suppose I’m a manager of some software company very interested in what Rust is providing. I’m learning that Rust ecosystem and find out sometimes lots of external crates are necessary for a simple task (e.g. regexes). I will soon ask: “who’s supporting those crates? If a crate is not supported or developed anymore, how to get support and from whom?”. These are legitimate questions any software manager will ask, as well as skilled people availability.

Once again, this is a constructive criticism and I love Rust. My opinion is that you can’t publicly advertise for safety features for which you necessarily need to download external packages. C++ and D standard library is large, 24V batteries included. But for sure older than Rust is.

1 Like

Well, since you’re mentioning C++, note that its standard library has historically been very lean too. Many high-level features like regexes are C++11 additions which only landed in mainstream compilers a couple years ago, and “classic” standard library features of other languages like XML and JSON support (or even TCP/IP sockets !) are still absent from the STL.

As surprising as it may sound today, old C++ standard revisions did not even have threads or hashmaps in their standard libraries, and yet they were nonetheless extremely successful in use cases ranging from operating system development to video games and high-frequency trading.

The same can be said of C, whose standard library is even smaller than C++98’s was. Many of the “libc” functions that are typically considered to belong to the standard C library are actually Posixisms or Linuxisms which are not supported on all operating systems, and may be quite badly emulated on some (asynchronous disk I/O on Linux being a classic example).

D never really achieved very broad industry adoption as far as I know, so I’m not sure if its community ever tackled this problem.


I think the way the C/++ situation historically worked out is that either the maintainers of external libraries or third-party companies like Linux distribution maintainers offered support contracts for heavily used external libraries (and open-source C/++ compilers, for that matter). A similar strategy could probably be successful for Rust.

But overall, it seems to me that by the standard of other bare-metal-friendly programming languages (native binaries & no GC), Rust’s standard library isn’t unusually thin. If anything, it is a bit thicker than the norm, though the existence of #[no_std] ensures that this doesn’t cause too many portability problems in embedded environments.

7 Likes

Why don’t you ask it for stdlib too? Surely because you trust the core team. But many of those “external libraries” are supported or even maintained by the core team too! If you want some lost of them, rust-lang-nursery is a place for libraries with extra care from them. But it’s not a complete list of it, so always check the contributors to know if it’s supported by trusted people.

2 Likes

For sure I trust the core team. I’m ok for downloading crates for specific needs, but my opinion is that basic and common (like regex) features should be in std. Regex is standard is all modern languages including Kotlin native. The Rust regex crate is depending on at least 5 other crates, not counting recursive dependencies.

I wholeheartedly hope that Rust will succeed. I’m just wondering if it will. Being a favorite’s dev language doesn’t make necessarily a success. It should be accepted and used by the industry.

As for C+, several boost libs are now in the std. But C++ has a long history and background.

In other languages useful stuff is pulled into std to be easy to use, because dependencies are a pain there. In Rust, writing use regex is as easy as use std::regex.

For Rust’s success being lean is also important. People already complain that “Hello World” is 700KB. It’d be worse if it was 700KB + regex library + kitchen sink.

2 Likes

@kornel I don’t think that dependency is specially painful in Java, D, Kotlin…

Anyway we can discuss hours but I don’ know how I can change my mind because the more I use Rust, the more I’m convinced. This is just my opinion. Downloading tons of crates to achieve a simple task is not my vision of simplicity specially when it comes to use an external crate to fulfill a simple requirement :wink:

Coming back to my problem, the most I can achieve without an external crate is:

fn parallel_sum<T>(v: Vec<T>, nb_threads: usize) -> T
where
    T: 'static + Send + Sync + Debug + AddAssign + Default + Copy,
{
    // this vector will hold created threads
    let mut threads = Vec::new();

    // need to arced the vector to share it
    let arced = Arc::new(v);

    // this channel will be use to send values (partial sums) for threads
    let (sender, receiver) = mpsc::channel::<T>();

    // create requested number of threads
    for thread_number in 0..nb_threads {
        // increment ref count, will be moved into the thread
        let arced_cloned = arced.clone();

        // each thread gets its invidual sender
        let thread_sender = sender.clone();

        // create thread and save ID for future join
        let child = thread::spawn(move || {
            // initialize partial sum
            let mut partial_sum: T = T::default();

            // this line doesn't compile:
            // partial_sum = arced_cloned.into_iter().sum();

            // trivial old style loop
            for i in 0..arced_cloned.len() {
                //
                if i % nb_threads == thread_number {
                    partial_sum += *arced_cloned.get(i).unwrap();
                }
            }

            // send our result to main thread
            thread_sender.send(partial_sum).unwrap();
            
            // print out partial sum
            println!(
                "thread #{}, partial_sum of modulo {:?} = {:?}",
                thread_number, thread_number, partial_sum
            );
        });
        
        // save thread ID
        threads.push(child);
    }
    
    // wait for children threads to finish
    for child in threads {
        let _ = child.join();
    }
    
    // terminate sender and get final sum
    //drop(sender);

    let mut total_sum = T::default();
    for _ in 0..nb_threads {
        // main thread receives the partial sum from threads
        let partial_sum = receiver.recv().unwrap();

        // and get the final total sum
        total_sum += partial_sum
    }
    
    total_sum
}

Probably sup-optimal but compiling and working. I found it incredibly painful for sharing an immutable value, not even touching mutation.

Thanks to @cuviper and this thread Why does thread::spawn need static lifetime for generic bounds? for a better understanding.

May not be painful, but with Rust it is painless. In the vast majority of cases you just stick a line in Cargo.toml and you’re done. Just use the crate as if it were another module to your crate (in the 2018 edition).

1 Like

There’s no need to use channels.

use std::sync::Arc;
use std::thread::spawn;
use std::cmp::min;
use std::ops::AddAssign;

fn main() {
    let mut vec = Vec::with_capacity(1000000);
    for i in 0..1000000u64 {
        vec.push(i*i);
    }
    let sum: u64 = vec.iter().cloned().sum();
    println!("local:    {}", sum);
    println!("parallel: {}", parallel_sum(vec, 11));
}


fn parallel_sum<T>(v: Vec<T>, nb_threads: usize) -> T
where
    T: 'static + Send + Sync + AddAssign + Default + Copy,
{
    if nb_threads == 0 { panic!("At least one thread required."); }
    if nb_threads > v.len() { panic!("More threads than items in vector."); }
    if v.len() == 0 { return T::default(); }

    // divide round up
    let items_per_thread = (v.len()-1) / nb_threads + 1;

    let arc = Arc::new(v);
    let mut threads = Vec::with_capacity(nb_threads);

    for i in 0..nb_threads {
        let data = arc.clone();
        let thread = spawn(move || {
            let from = i * items_per_thread;
            let to = min(from + items_per_thread, data.len());

            let mut sum = T::default();
            for v in &data[from..to] {
                sum += *v;
            }
            sum
        });
        threads.push(thread);
    }
    let mut sum = T::default();
    for t in threads {
        sum += t.join().expect("panic in worker thread");
    }
    sum
}
4 Likes

@alice Thanks for the tip :wink:

It was also an educational example to use channels. I’ll probably keep it in my article, but anyway good to know this method.

Channels are a prime example why std is better off to be small.

The std channels are slower and less flexible than the crossbeam crate. The std channel has even a rare crasher bug that has no fix. There was a plan to either replace std implementation with crossbeam’s (but not fully, since old naming and limitations have to stay for back compatibility) or just totally deprecate them and tell people to install crossbeam.

4 Likes

Yes, ::std represents a version 1.x.y that will never be able to reach 2.0 since it needs to remain backwards compatible forever. Having an ecosystem based on such a library just to save a few lines in a configuration file is not be the best choice for the long run.

2 Likes

@kornel: do you mean there’s a bug in the current version of std which won’t be ever fixed ?

@yandros: I never meant to save one line in the Cargo.toml. It’s the fact to shift essential features like regexes or rand to external crates I’m challenging.

They are not essential to everyone, and they aren’t needed to build a vocabulary like Vec<_> is. They are also massively complicated, so having them in an external crate means that it is fine if there is mistake, because we can fix it. If we have a mistake in std, we may not be able to fix it. This is much worse than not having it in std.

1 Like

@KrishnaSannasi This is your opinion, not mine. I think we can stop here this debate :wink:

1 Like

Bypassing the borrow checker for things like this is trivial; just use slice::as_ptr to get a raw pointer and do the sum the way you would do it in C. No need for external crates or Arc. You should, of course, be careful that you understand why it’s safe to do so, though. You essentially need to manually enforce that the threads are scoped, or at least that their access to the shared memory is scoped.

Avoiding unsafe is admirable, but often overly complicated.

That is one reason why Rust is not a “batteries included” language, because it’s almost impossible to replace defective batteries if they are in std .

@dandyvica you seem to know about python, so I’d assume you know or at least have heard how much pain, work, and frustration upgrading from python 2 to python 3 has been. Fixing / replacing broken batteries in the Python standard library is not the main reason for that, but it is definitely partially responsible for it. You also seem to be familiar with D, which ran into this exact same problem and the fix wasn’t easy. The D language had two incompatible standard libraries for a while, and this almost killed the language.

So I think everybody agrees with the part of your argument that argues that the current solution has downsides: discovering which crates you can rely on for important projects and how dependable these crates are isn’t an easy thing to do.

On the other hand, having a “batteries included” standard library like Python and D, without a solution to the problem that split the Python ecosystem for a decade and almost killed the D programming language would be an irresponsible thing to do.

A “feature” of the current Rust solution is that, because it is so minimal, if someone were to discover a solution for this problem without downsides, chances are that we can just use it without breaking backward compatibility.

I am not aware of any good solutions to this problems - all the ones I’ve heard had downsides, but that’s certainly an interesting topic. I think most of the work in the Rust side has gone into improving crate discoverability on crates.io, displaying statistics there about usage, maintenance, etc. so that project managers can evaluate how well maintained a crate is, how many stakeholders it has, etc., having documentation for all crates available in docs.rs, so that you can easily inspect it when assessing a crate, etc. There is certainly more that could be done about this, and people are working on that.

5 Likes

@gnzlbg

Thanks for your analysis. I agree with most of your arguments. As for Python 3 migration, it didn’t prevent this language to be in the top 5.

I’m ok with your conclusion. Will it be enough for Rust to be used in the industry ? Only future will tell.

My fear is that Kotlin native, although still in beta and GC oriented, will take over Rust for non system programming projects.

That class of competition is good for all parties. Rust has led to improvements in Ada/SPARK, and there are Ada features that are desirable for Rust. Rust avoids almost all exposure to malware by construction (largely via Lifetimes and the much-maligned Borrow Checker). In the longer term, Rust will come out ahead of those other languages that do not deliver similar malware-avoidance by construction.

1 Like