Część 1

Oczywiście niezmienność minimalizuje potrzebę blokowania w programowaniu wieloprocesorowym, ale czy eliminuje tę potrzebę, czy też są przypadki, w których sama niezmienność nie wystarczy? Wydaje mi się, że można jedynie odroczyć przetwarzanie i enkapsulować stan tak długo, zanim większość programów będzie musiała coś ZROBIĆ (zaktualizować magazyn danych, wygenerować raport, zgłosić wyjątek itp.). Czy takie działania zawsze można wykonać bez blokad? Czy samo działanie polegające na wyrzuceniu każdego obiektu i utworzeniu nowego zamiast zmiany oryginału (prymitywny pogląd na niezmienność) zapewnia absolutną ochronę przed rywalizacją między procesami, czy też są przypadki narożne, które nadal wymagają blokowania?

Wiem, że wielu funkcjonalnych programistów i matematyków lubi mówić o „braku efektów ubocznych”, ale w „prawdziwym świecie” wszystko ma efekt uboczny, nawet jeśli jest to czas potrzebny na wykonanie instrukcji maszynowej. Interesuje mnie zarówno odpowiedź teoretyczna / akademicka, jak i odpowiedź praktyczna / rzeczywista.

Jeśli niezmienność jest bezpieczna, biorąc pod uwagę pewne granice lub założenia, chcę wiedzieć, jakie dokładnie są granice „strefy bezpieczeństwa”. Niektóre przykłady możliwych granic:

• I / O
• Wyjątki / błędy
• Interakcje z programami napisanymi w innych językach
• Interakcje z innymi maszynami (fizycznymi, wirtualnymi lub teoretycznymi)

Specjalne podziękowania dla @JimmaHoffa za komentarz, który rozpoczął to pytanie!

Część 2

Programowanie wieloprocesorowe jest często stosowane jako technika optymalizacji - w celu przyspieszenia działania kodu. Kiedy szybciej jest używać zamków kontra niezmienne obiekty?

Biorąc pod uwagę ograniczenia określone w prawie Amdahla , kiedy możesz osiągnąć lepszą ogólną wydajność (z uwzględnieniem pojemnika na śmieci lub bez niego) w przypadku obiektów niezmiennych w porównaniu z blokowaniem obiektów zmiennych?

Podsumowanie

Łączę te dwa pytania w jedno, aby spróbować ustalić, gdzie znajduje się ramka graniczna dla Niezmienności jako rozwiązania problemów z wątkami.

To dziwnie sformułowane pytanie, które jest naprawdę bardzo szerokie, jeśli zostanie udzielona pełna odpowiedź. Zamierzam skupić się na wyjaśnieniu niektórych szczegółów, o które pytasz.

Niezmienność jest kompromisem. Utrudnia to niektóre operacje (szybka modyfikacja stanu w dużych obiektach, budowanie fragmentów obiektów, utrzymanie stanu pracy itp.) Na korzyść innych (łatwiejsze debugowanie, łatwiejsze rozumowanie zachowania programu, nie martwiąc się o rzeczy zmieniające się pod tobą podczas pracy jednocześnie itp.). To ostatnie, na którym zależy nam to pytanie, ale chcę podkreślić, że jest to narzędzie. Dobre narzędzie, które często rozwiązuje więcej problemów niż powoduje (w większości nowoczesnych programów), ale nie srebrną kulę ... Nie coś, co zmienia wewnętrzne zachowanie programów.

Co ci to daje? Niezmienność daje ci jedno: możesz swobodnie czytać obiekt niezmienny, nie martwiąc się o jego stan zmieniający się pod tobą (zakładając, że jest on naprawdę głęboko niezmienny ... Posiadanie niezmiennego obiektu ze zmiennymi elementami jest zwykle przełomem). Otóż ​​to. Uwalnia cię od konieczności zarządzania współbieżnością (za pomocą blokad, migawek, partycjonowania danych lub innych mechanizmów; oryginalne pytanie skupia się na blokadach jest ... Niepoprawne, biorąc pod uwagę zakres pytania).

Okazuje się jednak, że wiele rzeczy czyta obiekty. IO działa, ale samo IO zwykle nie radzi sobie dobrze z jednoczesnym użyciem. Prawie całe przetwarzanie działa, ale inne obiekty mogą być zmienne lub samo przetwarzanie może wykorzystywać stan, który nie jest przyjazny dla współbieżności. Kopiowanie obiektu jest dużym ukrytym problemem w niektórych językach, ponieważ pełna kopia (prawie) nigdy nie jest operacją atomową. Tutaj pomagają ci niezmienne obiekty.

Wydajność zależy od Twojej aplikacji. Zamki są (zwykle) ciężkie. Inne mechanizmy zarządzania współbieżnością są szybsze, ale mają duży wpływ na twój projekt. Ogólnie rzecz biorąc , wysoce współbieżna konstrukcja wykorzystująca niezmienne obiekty (i unikająca ich słabości) będzie działała lepiej niż wysoce współbieżna konstrukcja, która blokuje zmienne obiekty. Jeśli twój program jest lekko współbieżny, to zależy i / lub nie ma znaczenia.

Ale wydajność nie powinna być twoją największą troską. Pisanie współbieżnych programów jest trudne . Debugowanie współbieżnych programów jest trudne . Niezmienne obiekty pomagają poprawić jakość programu, eliminując możliwość ręcznego wprowadzenia zarządzania współbieżnością. Ułatwiają debugowanie, ponieważ nie próbujesz śledzić stanu w równoległym programie. Ułatwiają projektowanie, usuwając w ten sposób błędy.

Podsumowując: niezmienność pomaga, ale nie eliminuje wyzwań potrzebnych do prawidłowej obsługi współbieżności. Ta pomoc jest zazwyczaj wszechobecna, ale największe korzyści odnoszą się raczej do jakości niż do wydajności. I nie, niezmienność nie usprawiedliwia magicznie zarządzania współbieżnością w Twojej aplikacji, przepraszam.

Funkcja, która przyjmuje pewną wartość i zwraca inną wartość, i nie zakłóca niczego poza funkcją, nie ma skutków ubocznych, a zatem jest bezpieczna dla wątków. Jeśli chcesz zastanowić się, jak sposób działania funkcji wpływa na zużycie energii, jest to inny problem.

Zakładam, że masz na myśli maszynę Turing-complete, która wykonuje jakiś dobrze zdefiniowany język programowania, w którym szczegóły implementacji są nieistotne. Innymi słowy, nie powinno mieć znaczenia, co robi stos, jeśli funkcja, którą piszę w wybranym języku programowania, może zagwarantować niezmienność w obrębie tego języka. Nie myślę o stosie, kiedy programuję w języku wysokiego poziomu, i nie powinienem tego robić.

Aby zilustrować, jak to działa, przedstawię kilka prostych przykładów w języku C #. Aby te przykłady były prawdziwe, musimy poczynić kilka założeń. Po pierwsze, że kompilator przestrzega specyfikacji C # bez błędów, a po drugie, że produkuje poprawne programy.

Powiedzmy, że chcę prostej funkcji, która akceptuje kolekcję ciągów i zwraca ciąg będący konkatenacją wszystkich ciągów w kolekcji oddzielonych przecinkami. Prosta, naiwna implementacja w języku C # może wyglądać następująco:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    string result = string.Empty;
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result += s;
        else
            result += ", " + s;
    }
    return result;
} 

Ten przykład jest niezmienny, prima facie. Skąd to wiem? Ponieważ stringobiekt jest niezmienny. Jednak wdrożenie nie jest idealne. Ponieważ resultjest niezmienny, nowy obiekt ciągu musi być tworzony za każdym razem przez pętlę, zastępując oryginalny obiekt resultwskazujący. Może to negatywnie wpłynąć na prędkość i wywrzeć presję na śmieciarz, ponieważ musi on wyczyścić wszystkie te dodatkowe łańcuchy.

Powiedzmy, że to robię:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    var result = new StringBuilder();
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result.Append(s);
        else
            result.Append(", " + s);
    }
    return result.ToString();
} 

Zauważ, że mam wymienić string resultz zmienny obiektu StringBuilder. Jest to o wiele szybsze niż w pierwszym przykładzie, ponieważ nowy ciąg nie jest tworzony za każdym razem przez pętlę. Zamiast tego obiekt StringBuilder po prostu dodaje znaki z każdego łańcucha do zbioru znaków i generuje całość na końcu.

Czy ta funkcja jest niezmienna, nawet jeśli StringBuilder jest zmienny?

Tak to jest. Czemu? Ponieważ za każdym razem, gdy ta funkcja jest wywoływana, tworzony jest nowy StringBuilder, właśnie dla tego wywołania. Więc teraz mamy czystą funkcję, która jest bezpieczna dla wątków, ale zawiera zmienne komponenty.

Ale co jeśli to zrobię?

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;

    public string ConcatenateWithCommas(ImmutableList<string> list)
    {
        foreach (string s in list)
        {
            if (isFirst)
                result.Append(s);
            else
                result.Append(", " + s);
        }
        return result.ToString();
    } 
}

Czy ta metoda jest bezpieczna dla wątków? Nie, nie jest. Czemu? Ponieważ klasa utrzymuje teraz stan, od którego zależy moja metoda. W metodzie występuje teraz warunek wyścigu: jeden wątek może się modyfikować IsFirst, ale inny wątek może wykonać pierwszy Append(), w którym to przypadku mam teraz przecinek na początku mojego ciągu, którego nie powinno tam być.

Dlaczego mógłbym chcieć to zrobić w ten sposób? Cóż, może chcę, aby wątki gromadziły ciągi w moim, resultbez względu na kolejność lub w kolejności, w której wątki przychodzą. Może to rejestrator, kto wie?

W każdym razie, aby to naprawić, umieściłem lockoświadczenie wokół wewnętrznych elementów metody.

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;
    private static object locker = new object();

    public string AppendWithCommas(ImmutableList<string> list)
    {
        lock (locker)
        {
            foreach (string s in list)
            {
                if (isFirst)
                    result.Append(s);
                else
                    result.Append(", " + s);
            }
            return result.ToString();
        }
    } 
}

Teraz znów jest bezpieczny dla wątków.

Jedynym sposobem, w jaki moje niezmienne metody mogłyby nie być bezpieczne dla wątków, jest to, że metoda w jakiś sposób przecieka część jej implementacji. Czy to może się zdarzyć? Nie, jeśli kompilator jest poprawny, a program jest poprawny. Czy kiedykolwiek będę potrzebować blokad takich metod? Nie.

Aby zapoznać się z przykładem, w jaki sposób można wyciec wdrożenie w scenariuszu współbieżności, zobacz tutaj .

Nie jestem pewien, czy zrozumiałem twoje pytania.

IMHO odpowiedź brzmi tak. Jeśli wszystkie twoje obiekty są niezmienne, nie potrzebujesz żadnych blokad. Ale jeśli chcesz zachować stan (np. Wdrażasz bazę danych lub musisz agregować wyniki z wielu wątków), musisz użyć zmienności, a zatem także blokad. Niezmienność eliminuje potrzebę blokad, ale zwykle nie można sobie pozwolić na zastosowanie całkowicie niezmiennych aplikacji.

Odpowiedź na część 2 - zamki powinny być zawsze wolniejsze niż brak zamków.

Hermetyzacja wiązki stanów pokrewnych w pojedynczym zmiennym odwołaniu do niezmiennego obiektu może umożliwić przeprowadzenie wielu rodzajów modyfikacji stanu bez blokady za pomocą wzorca:

do
{
   oldState = someObject.State;
   newState = oldState.WithSomeChanges();
} while (Interlocked.CompareExchange(ref someObject.State, newState, oldState) != oldState;

Jeśli oba wątki spróbują zaktualizować someObject.statejednocześnie, oba obiekty odczytają stary stan i ustalą, jaki byłby nowy stan bez wzajemnych zmian. Pierwszy wątek, który wykona CompareExchange, zapisze, co według niego powinien być następny stan. Drugi wątek odkryje, że stan nie jest już zgodny z tym, co wcześniej odczytał, a zatem ponownie obliczy właściwy następny stan systemu z wprowadzonymi zmianami pierwszego wątku.

Ten wzór ma tę zaletę, że wątek, który zostanie utworzony, nie może blokować postępu innych wątków. Ma tę dodatkową zaletę, że nawet w przypadku silnej rywalizacji, pewien wątek zawsze będzie robił postępy. Ma jednak tę wadę, że w przypadku sporów wiele wątków może poświęcić dużo czasu na pracę, którą ostatecznie odrzuci. Na przykład, jeśli 30 wątków na oddzielnych procesorach spróbuje jednocześnie zmienić obiekt, ten odniesie sukces przy pierwszej próbie, jeden na drugim, jeden na trzecim itd., Tak że każdy wątek kończy średnio około 15 prób zaktualizować swoje dane. Użycie blokady „doradczej” może znacznie poprawić sytuację: zanim wątek podejmie próbę aktualizacji, powinien sprawdzić, czy ustawiony jest wskaźnik „rywalizacji”. W takim razie, przed wykonaniem aktualizacji powinien uzyskać blokadę. Jeśli wątek podejmie kilka nieudanych prób aktualizacji, powinien ustawić flagę rywalizacji. Jeśli wątek, który próbuje zdobyć zamek, stwierdzi, że nikt inny nie czekał, powinien wyczyścić flagę rywalizacji. Zauważ, że blokada tutaj nie jest wymagana dla „poprawności”; kod działałby poprawnie nawet bez niego. Celem blokady jest zminimalizowanie czasu, jaki kod spędza na operacjach, które prawdopodobnie nie zakończą się powodzeniem.

Zaczynasz od

Wyraźnie niezmienność minimalizuje potrzebę blokowania w programowaniu wieloprocesorowym

Źle. Musisz uważnie przeczytać dokumentację dla każdej klasy, z której korzystasz. Na przykład const std :: string w C ++ nie jest bezpieczny dla wątków. Niezmienne obiekty mogą mieć stan wewnętrzny, który zmienia się podczas uzyskiwania do nich dostępu.

Ale patrzysz na to z zupełnie błędnego punktu widzenia. Nie ma znaczenia, czy obiekt jest niezmienny, czy nie, ważne jest, czy go zmienisz. To, co mówisz, przypomina powiedzenie „jeśli nigdy nie podejmiesz egzaminu na prawo jazdy, nigdy nie możesz stracić prawa jazdy na jazdę pod wpływem alkoholu”. To prawda, ale raczej nie ma sensu.

Teraz w przykładowym kodzie ktoś napisał za pomocą funkcji o nazwie „ConcatenateWithCommas”: Jeśli dane wejściowe byłyby zmienne i użyłeś blokady, co byś zyskał? Jeśli ktoś spróbuje zmodyfikować listę, a Ty spróbujesz połączyć łańcuchy, blokada może zapobiec awarii. Ale nadal nie wiesz, czy połączysz łańcuchy przed czy po zmianie innego wątku. Więc twój wynik jest raczej bezużyteczny. Wystąpił problem niezwiązany z blokowaniem i którego nie można naprawić za pomocą blokady. Ale jeśli użyjesz niezmiennych obiektów, a drugi wątek zastąpi cały obiekt nowym, użyjesz starego obiektu, a nie nowego obiektu, więc wynik jest bezużyteczny. Musisz pomyśleć o tych problemach na faktycznym poziomie funkcjonalnym.