GSoC: Linked List || Blog post by Chetan Karwa || #6

Projects GSoC-2021
1

Greetings Everyone,

Progress in the past week:

  • Implemented pop() and remove() functionality.

  • I also have some results regarding parallel deletion linked list(list of list implementation)
    1.First of all, I was using cpu_time regarding which Arjen mentioned that it returns the sum of computation time taken by each thread.
    2.So a better fit for this was to use wall clock time. (system_clock)
    3.Though the test results still didn’t match our expectations and the computation time actually increased instead of decreasing.
    4.Arjen had a possible reason for this abrupt outcome
    5.A detailed note on what was the test program and the output received can be found here.

  • One explanation for this: the OS’s memory management gets in the way. It may or may not be threaded itself, or it needs to take a lot of care to ensure things remain consistent. That would be a valuable lesson: calculations benefit from multithreading, but data structures much less. Well, that may be cutting corners a bit, but that would be my conclusion.

  • For now, we have decided to drop the plan of parallel computing because:
    1.The outputs are not desired
    2.We discussed the use of parallel computing in stdlib and how does that affect a user in general. (Maybe the user can use stdlib in some program that is already working on parallel threads so he might run into the complexity of nested parallel programs)

  • In addition to all these, thanks to @themos to let me know of the compilations errors that he faced in the NAG compiler which were overlooked in gfortran compiler. I will fix all such possible errors.

For some personal reasons, I couldn’t achieve my goals for the past week.
So I intend to finish them and also set extra tasks for this week.

Plan for the coming week:

  • Implement insert() API.
  • Open an issue on Fortran-Lang stdlib.
  • Make a report of testing the list_of_list module to hold a million or more strings of 20 to 1000 characters.
  • Fix the compilation errors (NAG).

Thank you

1 Like
2

Hello Chetan,

it is nice to observe your progress.

Browsing through the ACM Fortran Forum today I noticed there are some articles that might be of interest to you:

Meissner, L. P. (1997, August). Fortran 90 & 95 linked list operations: managing an ordered list with pointers to pointers. In ACM SIGPLAN Fortran Forum (Vol. 16, No. 2, pp. 18-22). New York, NY, USA: ACM. Fortran 90 & 95 linked list operations: managing an ordered list with pointers to pointers: ACM SIGPLAN Fortran Forum: Vol 16, No 2

Blevins, J. R. (2009, December). A generic linked list implementation in Fortran 95. In ACM SIGPLAN Fortran Forum (Vol. 28, No. 3, pp. 2-7). New York, NY, USA: ACM. https://doi.org/10.1145/1667140.1667141

The website fortran.com previously owned by Walt Brainerd used to offer a book:

Loren P. Meissner (1998). Fortran 90 & 95 Array and Pointer Techniques: Objects, Data Structures, and Algorithms.

I’ve seen some copies published on the internet in clear violation of the original copyright agreement.

2 Likes